LeetCode - 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.

思路：

1. 不让用空间换时间，说明不是dp，所以基本只让过一两遍数组，一边过一遍直接in place的改动数组（不让生成新数组）
2. 既然是大部分不missing，所以可以用index来直接和元素产生关系。
3. 试图让A[i]这个值x的index是x – 1，即每个index身上的元素都是index本身+1。所以{1 2 3}就是理想中的新数组，{1 5 3}就说明缺2。

算法：

1. 如果A[i]不在自己该在的地方，就想办法把他换到该在的地方。如果A[i]是<=0或者A[i]比数组长度还大，说明没有它该在的地方，那就skip他，弄下一个（不用担心当前位置被它占了，如果后面有想在这个位置的正整数，它会被换走的）
2. A[i]和A[A[i] – 1]换，然后继续回到i，接着换，直到第一种情况满足。但是如果这俩数一样，换也没用，就别原地打转了。
3. 最后过一遍shift过的array，第一个不在原位的就是。

 

public int firstMissingPositive(int[] A) {
    for(int i=0; i<A.length; i++) {
        if(A[i]!=i+1 && A[i]>0 && A[i]<=A.length && A[i]!=A[A[i]-1]) {
            swap(A, i, A[i]-1);
            i--; //回到刚才这位接着做
        }
    }
    for(int i=0; i<A.length; i++) {
        if(A[i] != i+1) return i+1;
    }
    return A.length+1;
}
private void swap(int[] A, int i, int j) {
    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}

文章来自：

https://leetcodenotes.wordpress.com/2013/07/17/first-missing-positive/

图片来自：

http://www.cnblogs.com/AnnieKim/archive/2013/04/21/3034631.html