sourcecode

Sunday, February 8, 2015

First Missing Positive

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for(int ii = 0; ii < n; ++ii) {
            while (A[ii] != ii + 1 ) {
                if (A[ii] <= 0 || A[ii] > n || A[ii] == A[A[ii] - 1]) {
                    A[ii] = -1;
                    break;
                }
                swap(A, ii, A[ii]-1);
            }
        }
       
        for (int ii = 0; ii < n; ++ii) {
            if (A[ii] != ii+1) return ii+1;
        }
        return n+1;
    }
   
    void swap(int A[], int here, int other) {
        int temp = A[here];
        A[here] = A[other];
        A[other] = temp;
        return;
    }
};

No comments: