First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,

Given [1,2,0] return 3,

and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

数组哈希法

复杂度

O(N) 时间 O(1) 空间

思路

这道题先得理解深刻，再做

对于一个数组，长度为n,我们在最后返回的答案肯定是[1,n+1]闭区间范围内，超出这个区间不可能是答案，跳过即可我们要做的就是，两步走：1.把数组中有可能是答案的数([1,n+1]闭区间内的数)放在正确的位置上：num放在下标为num-1的位置上，比如4放在下标为3的位置上，注意有可能是答案的数才放，此时不会数组越界。2.最后在这些可能的位置上找答案，这些位置是0到n-1。举几个例子：[5,6,7],答案：1[5]，答案：1[-5],答案：1[0]，答案：1[1]，答案：2[2,2]，答案：1注意最后这个例子，对于第一个2，这个数在答案区间内，可是我们发现在他应该出现的位置上已经是他了，那么我们视当前这个位置的2不是答案，跳过这个。这个特例需要注意哟~

注意

注意[2,2]这种情况哟

代码

public class Solution {    public int firstMissingPositive(int[] nums) {        for (int i = 0; i < nums.length; ) {            int n = nums[i];            if (n >= 1 && n <= nums.length + 1 && nums[n - 1] != n) {//这个数在答案区间                int tmp = nums[n - 1];                nums[n - 1] = n;                nums[i] = tmp;            } else {    //不在答案区间跳过不管                i++;            }        }        for (int i = 1; i < 1 + nums.length; i++) {            if (nums[i - 1] != i)                return i;        }        return nums.length + 1;    }}