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.

关键是只允许常数空间。这里要突破思维定势，要改变给定数组的结构。

对于A[i]，如果A[i] > 0 && A[i] <= n，则将它与A[i] – 1 位置的元素互换位置。

遍历一遍后，再从左到右找到第一个A[i] != i + 1的元素，i + 1即为所求。

这里实际上是用o(n)的时间和对A进行了排序。之所以比快排o(nlogn)还快，是因为它只对0-n之间的数字有效。

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        int i = 0;
        while(i < n){
            if(A[i] > 0 && A[i] <= n && A[i] != i + 1 && A[i] != A[A[i] - 1]){
                swap(A, i, A[i] - 1);
            }
            else{
                i++;
            }
        }
        for(int i = 0; i < n; i++){
            if(A[i] != i + 1){
                return i + 1;
            }
        }
        return n + 1;
    }
    void swap(int A[], int a, int b){
        int tmp = A[a];
        A[a] = A[b];
        A[b] = tmp;
    }
};