First Missing Positive

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

Example

Given [1,2,0] return 3, and [3,4,-1,1] return 2.

Challenge

Your algorithm should run in O(n) time and uses constant space.

----------------- thinking -----------------
e.g. [1,1] --> duplications
e.g. [-1, 4, 2, 1, 9, 10] ->larger than A's size() numbers
------------------ codes -------------------
class Solution {
public:
    /**  
     * @param A: a vector of integers
     * @return: an integer
     */
    int firstMissingPositive(vector<int> A) {
        // write your code here
        if (A.size() == 0) return 1;
        // re-arrage A by index
        for (int i = 0; i < A.size(); i++) {
            while (A[i] != i + 1 && A[i] > 0 && A[i] <= A.size() && A[A[i] - 1] != A[i]) {
                int tmp = A[i];
                A[i] = A[A[i] - 1];
                A[tmp-1] = tmp;
            }
        }
        int i = 0;
        while (A[i] == i + 1) {
            i++;
        }
        return i+1;
    }
};