First Missing Positive

Q:
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.
A:
就是求和，然后-------哎，可是有重复啊！！！！！！！！
考虑到负值的存在，因此我们需要 设一个值，来记录positive number 的个数。
另外， 记录till now max

Remember,  we are required to find the first,  i.e.  there might exist multiple missing positive integer.

例如： int [] A = {3,3,4,1,1,1};
基本的思路来源于：当设置都封死了我们利用现有算法，也不让用额外的空间， 因此，我们只能更改已给的空间。
哎，这样不行，那样也不行。就只能考虑，在A数组上更改了。

基本思路是： 用地址代表数字内容。 亦即，A[i] 的内容，更改为 i+1.
首先，对于负数。我们统统 set to be zero. 对于正数，改成其相反数。

因此，当遇到一个数字为负值。首先该位置设0， 表明我们 经历过了。
紧接着，就找value 对应的position  , 如果该position 已经为正， 则我们现在遇到的这个数字，已经是重复的了。 直接跳过。 如果 A[val -1] < 0。 则继续调整。
经过分析，我们可以看到。虽然for loop 里有while 循环，但是，每个while都至少set 一个A的位置为非负。  因此，总的次数，不超过2*A.length()的。
也就保证了O（n）的效率。

public class Solution { 
    public int firstMissingPositive(int[] nums) {
        // find a value, called val, put it on position nums[val -1]
        int n = nums.length;
        for(int i =0;i< n;i++){
            int val = nums[i];
            if(val<=0 || val == i+1 || val >= n || nums[val-1] == val)
                continue;
            // swap these two position
            int tmp = nums[i];
            nums[i] = nums[val-1];
            nums[val-1] = tmp;
            i--;
        }
        for(int i =0;i< n;i++){
            if(nums[i] != i+1)
                return i+1;
        }
        return nums.length+1;
    }
}
 

Mistakes:
1： 没有考虑重复的情况。 例如A = [1, 1].
2:  找到解决方法后， 没有考虑输入为空的情况。 （其实考虑了，但是，直接用assert排除了)
3： 题意理解不透彻， given input A=[1,2]， the output is expected to be : 3


Learned:

----------------------------------第二遍------------
思路和上面的不一样：
简单来讲，就是对每一个位置， 如果错位排列的， 把其位置 调整过来。
记得调整的时候，要检查，是否是相同的数字，如果相同，则不必swap了（会有loop)

public class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i =0;i<nums.length;i++){
            if(nums[i]<=0 || nums[i] >n){
                nums[i] = -1;
            }else if(nums[i] != i+1){
                int nextPos = nums[i] - 1;
                if(nums[i]== nums[nextPos]){
                    nums[i] = -1;
                }else{// swap this two position
                    int tmp = nums[i];
                    nums[i] = nums[nextPos];
                    nums[nextPos] = tmp;
                }
                i--;
            }
        }
        // find the first position that is not a match
        for(int i =0;i<nums.length;i++)
            if(nums[i] != i+1)
                return i+1;
        return n + 1;
    }
}