Thursday, July 24, 2014

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.

bucket sort
public class Solution {
    public int firstMissingPositive(int[] A) {
        //Time: O(n)  Space: O(1)
        if (A == null || A.length == 0) {
            return 1;
        }
        
        for (int i = 0; i < A.length; i++) {
            while (A[i] > 0 && A[i] <= A.length && A[i] != i + 1) {
                int temp = A[i];
                //if same, don't need swap
                if (A[temp - 1] == A[i]) {
                    break;
                }
                A[i] = A[temp - 1];
                A[temp - 1] = temp;
            }
        }
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i + 1) {
                return i + 1;
            }
        }
        return A.length + 1;
    }
}

No comments:

Post a Comment