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.

Misunderstanding on the problem:

find the first missing positive, not the missing consecutive number !!!

i.e. 7 5 8 return 1 not 6

Solution:

zero based:

int firstMissingPositiveAnd0(int A[]) {
    int n = A.length;
    for (int i = 0; i < n; i++) {
        // when the ith element is not i
        while (A[i] != i) {
            // no need to swap when ith element is out of range [0,n]
            if (A[i] < 0 || A[i] >= n)
                break;

            //handle duplicate elements
            if(A[i]==A[A[i]])
                            break;
            // swap elements
            int temp = A[i];
            A[i] = A[temp];
            A[temp] = temp;
        }
    }

    for (int i = 0; i < n; i++) {
        if (A[i] != i)
            return i;
    }

    return n;
}

one based:

public int firstMissingPositive(int[] A) {
        int n = A.length;

        for (int i = 0; i < n; i++) {
            while (A[i] != i + 1) {
                if (A[i] <= 0 || A[i] >= n)
                    break;

                    if(A[i]==A[A[i]-1])
                            break;

                int temp = A[i];
                A[i] = A[temp - 1];
                A[temp - 1] = temp;
            }
        }

        for (int i = 0; i < n; i++){
            if (A[i] != i + 1){
                return i + 1;
            }
        }    

        return n + 1;
}