LeetCode-First Missing Positive

没想出来，想到了count sort，但是没想到怎样用常量空间的方法。

看了大神Annie Kim(https://github.com/AnnieKim/LeetCode)的代码，才豁然开朗，

也算有学习和总结到了一条规律：

凡是要求常量空间的题目要尽量利用题目中已有的空间！

这道题目很经典，非常好的面试题。

就算知道了方法以后，实现的时候也还是有一定的技巧的，

每个位置i都需要多次交换，直到A[i] = i + 1为止，不过对于A[i] > n的元素

可以先不管，最后再交换到最后！

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n == 0) {
            return 1;
        }
        int i = 0; 
        while (i < n) {
            if (A[i] != i + 1 && A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i]) {
                swap(A[i], A[A[i] - 1]);
            }
            else {
                ++i;
            }
        }
        for (i = 0; i < n; ++i) {
            if (A[i] != i + 1) {
                return (i + 1);
            }
        }
        return n + 1;
    }
};