First Missing Positive

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.

-------------------------- codes --------------------------------------
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]) {
                int tmp = A[i];
                A[i] = A[A[i]-1];
                // insteand of using A[A[i]-1] = tmp, because A[i] has been changed
                A[tmp-1] = tmp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (A[i] != i + 1) {
                return i+1;
            }
        }
        //bug here: e.g. [], [1]
        return n+1;
    }
};