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.

public int firstMissingPositive(int[] A) {
    if (A.length == 0) {
        return 1;
    }
    int i = 0;
    while (i < A.length) {
        if (A[i] != i + 1) {
            if (A[i] <= A.length && A[i] > 0 && A[A[i] - 1] != A[i]) {
                swap(A, i, A[i] - 1);
            } else {
                A[i] = 0;
                i++;
            }
        } else {
            i++;
        }
    }
    for (int j = 0; j < A.length; j++) {
        if (j + 1 != A[j]) {
            return j + 1;
        }
    }
    return A.length + 1;
}

public void swap(int[] nums, int a, int b) {
    int tmp = nums[a];
    nums[a] = nums[b];
    nums[b] = tmp;
}
FacebookTwitterGoogle+Share