wayetan
1/6/2014 - 5:29 AM

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.
 */
 
public class Solution {
    public int firstMissingPositive(int[] A) {
        if(A.length == 0)
            return 1;
        for(int i = 0; i < A.length; i++){
            if(A[i] > 0 && A[i] - 1 < A.length && A[i] - 1 != i && A[i] != A[A[i] - 1]) {
                int t = A[A[i] - 1];
                A[A[i] - 1] = A[i];
                A[i] = t;
                i--;
            }
        }
        for(int j = 0; j < A.length; j++){
            if(A[j] - 1 != j)
                return j + 1;
        }
        return A.length + 1;
    }
    
}