给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
class Solution {public int firstMissingPositive(int[] nums) {//将负数变成范围外的正数for(int i = 0; i < nums.length; i++){if(nums[i] <= 0)nums[i] = nums.length+1;}//将数组的值减一作为数组下标,此下标元素变为负数for(int i = 0; i < nums.length; i++){// System.out.print("//"+nums[i]);int index = Math.abs(nums[i]);if(index <= nums.length)//加绝对值是因为可能出现重复数变回正值nums[index-1] = -Math.abs(nums[index-1]);}//最后还是正数的元素,下标加一就是未出现的for(int i = 0; i < nums.length; i++){if(nums[i] > 0)return i+1;}//注意可能是最后一个return nums.length+1;}
}