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. http://leetcode.com/onlinejudge#question_41

leetcode_first_missing_positive.cpp

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