给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
*/
/*
* 题目大意：找到一个未排序序列中的第一个缺失的正数。简而言之，就是看1在不在这个序列中，如果不在的话输出1；
* 否则看2在不在这个序列中，如果不在的话输出2；否则看3在不在这个序列中
思路：
本题的一个难点就在 要求O(n)时间复杂度 O(1)空间复杂度 不允许申请新的空间
1.先说说O(n)空间复杂度的解法 利用HashSet存放所有的数组元素 然后从1开始 找到第一个不在set里面的元素 就是最小值
2.O(1)空间复杂度的解法
nums[i]代表该数在数组中应该处于第i个位置 对应数组的索引就是i-1 也就是nums[i]-1
举个例子，假设有序列[4,2,6,1,-3]，首先看第一个数4，它正确的位置应该是在序列的第4个位置（位置数从1开始，正确的位置是第一个位置放1，第二个位置放2，第三个位置放3……最后我们只要看哪个位置放的不是理想的数，
那么它就是第一个缺失的正数）。我们将4与第4个位置上的“1”进行交换，序列变成[1,2,6,4,-3]；接着我们还是
看第一个数，现在变成了“1”，它的确在它正确的位置，好了，我们再看第二个数2，也在正确的位置。第三个数6，
本来应该放在第6个位置，可是该序列总共就5个位置，所以不移动；第四个数4在它的正确位置，不动；第五个数是负数，
不动。最后，从前往后看，发现在第三个位置本该出现的3没有出现，所有该序列缺失的第一个正数是3。
//时间复杂度应为O(n)，并且只能使用常数级别的空间
public static int firstMissingPositive(int[] nums) {
int len=nums.length;
for (int i = 0; i < len; i++) {
//nums[i]代表该数在数组中应该处于第i个位置 对应数组的索引就是i-1 也就是nums[i]-1
//由于负数不考虑 所以nums[i]>0 而nums[i]如果大于数组长度 则也不用交换
while (nums[i]>0&&nums[i]<=len&&nums[i]!=nums[nums[i]-1]) {
swap(nums,i,nums[i]-1);
}
}
//操作完成之后 遍历 找到nums[i]第一个不等于i+1的点 结果就是i+1
for (int i = 0; i < len; i++) {
if (nums[i]!=i+1) {
return i+1;
}
}
//都符合要求了 说明数组的值是 1~nums.length 则返回
return len+1;
}
private static void swap(int[] nums, int i, int j) {
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
京公网安备 11010502036488号