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

leetcode_first_missing_positive.cpp

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