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,因为我们要找的是连续的正整数列,我们只需要将i的index上放入对应的i+1的数即可。

因为要求constant space,所以我们直接在输入的array里swap。
遍历这个array,一旦碰到i中存的不是i+1, 那么我们把A[i]和A[A[i] -1]换, 这样i中的元素就到了合适的地方,如果i中存的是负数或者是比整个A还大的数,或者换过来的数和原来的数一样,那么我们i++检查下一个。

这样一遍遍历完,用O(n)的时间,然后再遍历一遍,找到第一个不符合规则的数即可。如果所有数都符合规则,那么return n+1.

public class Solution {
    public int firstMissingPositive(int[] A) {
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i+1 && A[i] < A.length && A[i] > 0 && A[A[i] - 1] != A[i]) { // keep swap until nowhere to swap or match or swaping the same element
                swap(A, A[i] - 1, i);
                i--;
            }
        }
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i+1)
                return i+1;
        }
        return A.length + 1; // if every integer is present, return A.length + 1;
    }
    
    public void swap(int [] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

Notice that if the target position already contains the legal element, then we do not need to swap and increment to the next position

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] <= A.length) { // if it is out of the index range 
                if (A[A[i] - 1]-1 != A[i] - 1) {// if the target number is not legal than swap, otherwise skip
                    swap(A, i, A[i] - 1);
                    i--; //keep checking until A[i] can not satisfy, if swap out a legal number, skip
                }
            }
        }
        
        for (int i = 0; i < A.length; i++) {
            if (i != A[i] - 1)
                return i + 1;
        }
        return A.length + 1;
    }
    
    private void swap(int [] A, int i1, int i2) {
        if (A[i1] == A[i2])
            return ;
        int temp = A[i1];
        A[i1] = A[i2];
        A[i2] = temp;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s