Description

LeetCode 41

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

Note:

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

Analysis

From the description, we can find an important clue that the position and the value of the element have some relations. It every element is in its correct position, then there will not be missing number inside the scope of the sequence.

So first we should arrange the elements. If we find a position that has the wrong element but the element is a valid element that should be in the sequence, then swap it with the wrong element’s correct position. If the new element is still wrong but valid, do this again until the new element is correct or invalid. Implement this process for every element.

Now all the valid elements are in their correct positions. Just find the first position that has the wrong element which is of course an invalid element and return the correct element that should be in this position.

The time is \(O(n)\) and the space is \(O(1)\).

Solution

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

Reference

[1] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/FirstMissingPositive.java

1 Comment

Leave a Reply

Your email address will not be published. Required fields are marked *