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.

The challenging part of this problem is to 'uses constant space'. We need to find out how to manipulate the array itself to achieve this goal.

For A[n] to contain {1,2,3,4,......},  A[I]=I+1 or I = A[I]-1; If this condition doesn't hold, swap A[I] with A[A[I]-1] till we can't swap them anymore.

More specifically,
For n numbers, the answer must be in [1, n + 1].
1. If n numbers are 1, 2, 3, ..., n, then the answer is n + 1.
2. use a number x (x <= 0 || x > n) to replace a number in 1, 2, 3, ..., n. There must be a number less than n+1.

This is the key to write the following code.

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