题解 | #缺失的第一个正整数#
缺失的第一个正整数
http://www.nowcoder.com/practice/50ec6a5b0e4e45348544348278cdcee5
本题关键点在于：长度为n的数组，最小未出现整数一定是在[1,n+1]的闭区间内的
极限情况是：{1，2，3，4，5}那么最小整数就是n+1=6
一般情况：{1，3，4，5，6} 最小整数是2
其实这么思考，一个长度为n的数组，按照一个一个位置填充，极限情况就是把1～n个数字依次填充完，那么就是n+1是最小未出现。
1、Hash表法（不符合题意）
时间复杂度O(n)，空间复杂度O(n)---hash表的空间
思路：将所有的元素存入存入hash表，然后依次判断1～n+1哪个最小值没出现在hash表中，直接返回。
2、原地hash
时间复杂度O(n)，空间复杂度O(1)
思路：利用hash表的思想，将 x值 放到 下标为 x-1 的位置（交换位置）<也就是5放到下标为4的位置>，再进行一次遍历，看哪些下标不满足nums[i]-1==i，那就是未出现的值
for(int i= 0 ;i<nums.length;i++){
//我们只对nums[i]在[1,N],范围内的值就行操作，因为按照我们的规定
//nums[i]应该放在nums[i]-1的位置，正好能满足数组下标[0,n-1]的范围
// nums[nums[i]-1]!=nums[i]这个很关键，其实就是当前nums[i]位置的值x，那我看看nums[x-1]？=x
//千万不能写成nums[i-1]!=i(重复的情况下)
//假设是[1,1],当i=0的时候显然满足我们的情况不需要交换，跳到i=2，如果采用的是
//1、nums[i]-1?=i，那么 1-1！=1，一直交换一直死循环
//2、nums[nums[i]-1]?=nums[i]；nums[1-1]?=nums[1]=>1==1
//2其实就是：我现在位置上的值是x，那我看看x-1下标下是不是我当前这个值，如果是了，那就证明我重复了，没事我就不管了，只要这个位置满足这个条件就可以了，如果不在，那就要换一下
while (nums[i]>=1&&nums[i]<=nums.length&&nums[nums[i]-1]!=nums[i]){
swap(nums,nums[i]-1,i);
}
}
for(int i= 0 ;i<nums.length;i++){
if(nums[i]!=i+1){
return i+1;
}
}
//如果位置都排好了，你就上面说的极限情况
return nums.length+1;
}
public void swap(int[] nums,int i,int m){
int temp = nums[i];
nums[i] = nums[m];
nums[m] = temp;
}
3、巧妙的标记方法：
时间复杂度O(n)，空间复杂度O(1)
思路：
1、首先先将所有小于等于0的数换成 N+1
2、遍历数组，比如说nums[i]=1，那么我就要把nums[1-1]的值换成负数
3、再次遍历数组，观察第一个下标对应的值不是负数的那就证明是没出现过的，那就返回当前下标+1；
public int minNumberDisappeared (int[] nums) {
// write code here
//巧妙方法：
int n = nums.length;
//将所有小于等于0的变成n+1；
for(int i = 0;i<n;i++){
if(nums[i]<=0){
nums[i]=n+1;
}
}
for(int i = 0;i<n;i++){
//这里加绝对值是位了防止已经有其他元素将它变成了负数，那就要还原他与原本的值
int temp = Math.abs(nums[i]);
//范围是1～n的元素进行操作
if(temp>=1&&temp<=n){
//Math.abs(nums[temp-1])这里的绝对值是为了防止多个重复的数对他进行加负数操作
//那么它就会在 负 正 负 正这样交换，只要出现偶数个重复的，那就还是正，所以每次操作的时候都先把他变成正书再操作
nums[temp-1]=-Math.abs(nums[temp-1]);
}
}
for(int i = 0;i<n;i++){
if(nums[i]>0){
return i+1;
}
}
return n+1;
}
网易有道公司氛围 38人发布