Saturday, April 4, 2015

LeetCode [41] First Missing Positive

 41. First Missing Positive

Hard

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Follow up:

Your algorithm should run in O(n) time and uses constant extra space.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i=0; i<n; ++i){
            int v = nums[i];
            int index = v-1;
            //move v to position index such that nums[index]==index+1
            while(v>=1 && v<=n && nums[index]!=index+1){
                int t = nums[index];
                nums[index] = v;
                nums[i] = t;
                
                //move t to the right position if possible
                v = nums[i];
                index = v-1;
            }
        }

        for(int i=0; i<n; ++i){
            if(nums[i]!=i+1) return i+1;
        }
        return n+1;
    }
}

No comments:

Post a Comment