LeetCode 41 First Missing Positive

Posted on | In | 阅读

桶排序思想，一种理想情况下接近O(n)的排序算法

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

Example 1:

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

Example 2:

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

Example 3:

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

Note:

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

  • 假设这n个数就是1-n进行排序，即i应该放在nums[i-1]上
  • 扫描一遍数组，只要当前位置上的数不是在1-n之间并且没有正确摆放，就与正确位置上的数进行一次交换
  • 所有的数都会被扫描到一遍，每一次交换都会使得一个数到达它应该在的位置上，所以最多交换n次，扫描过后所有在1-n区间内的数都会被换到它应该在的位置上
  • 再从头扫描一遍数组，第一个放置错误的位置就是第一个缺失的数，如果都正确了，那么就是n+1缺失

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        if length == 0:
            return 1
        for i in range(length):
            while nums[i] > 0 and nums[i] <= length and nums[i] != i+1 and nums[i] != nums[nums[i]-1]:
                tmp = nums[nums[i]-1]
                nums[nums[i]-1] = nums[i]
                nums[i] = tmp
        
        for i in range(length):
            if nums[i] != i+1:
                return i+1
        return length+1