First Missing Positive, Leetcode 解题笔记

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.

因为有O(n)时间复杂度的要求,说明我们不能进行任何排序,因为最快的排序是O(nlogn)。第一反应是建立一个HashMap,但是还要求constant space,所以也不行。

网上找了找答案,发现最优解法如下:
We are required to use constant space. So we need to use the array. We can put the element, which value is i, in position i – 1. After we finishing doing this, we can go through the array to find the first missing positive integer.

For example, the original array is 3 4 -1 1. We will make it like 1 4 3 -1. And we can know the missing number is 2 easily.

代码不长,所以直接看代码理解:

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

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