LeetCode 筆記 - 41. First Missing Positive

Posted on
挑戰 LeetCode 經典困難題，在未排序的數列中找出沒出現過的最小正整數。本文實作符合時間複雜度 O(n) 與空間複雜度 O(1) 的原地置換演算法，透過將數值放到對應索引位置來解決問題。

題目在此 41. First Missing Positive

給一個未排序的數列，請問沒出現過的最小正整數是多少？

請給出 Time complexity $O(n)$, space complexity $O(1)$ 的解法

解題思維

這題的難點就在於怎麼在 $O(n)$ 的時間複雜度內解決。
既然都跟你說 $O(n)$ 了，那就不能用排序了，因為以現在時代的極限，排序的時間複雜度最快也是 $O(n \log n)$。image 106

所以重點就是怎麼在不排序的情況下，找出最小的正整數。

這題的解法連操作資料結構本身的複雜度都需要考慮進去，實作中我們使用 set 來儲存資料，因為 element in set 的時間複雜度是 $O(1)$，remove() 也是 $O(1)$。

Python 資料結構的時間複雜度可以參考 TimeComplexity - Python Wiki
更多資料結構的時間複雜度可以參考 Big-O Algorithm Complexity Cheat Sheet
NOTE: 而其中 set 可以對比到 Hash Table。

step 0: 先把 nums 轉成 set，標記 result = 1。
step 1: 讓 nums pop 出一個數字 n，請注意 pop 的同時也已經從 nums 中移除了。
step 2: 檢查 n - 1 是否在 set 中，如果在的話就 pop，並繼續檢查 n - 2 …，並記錄為 left，直到不存在。
step 3: 檢查 n + 1 是否在 set 中，如果在的話就 pop，並繼續檢查 n + 2 …，並記錄為 right，直到不存在。
step 4: 如果 left <= result <= right，代表 result 在 left 與 right 之間，所以 result 的值就是 right + 1。
step 5: 這時候你會發現其實 result 只要更新一次就可以了，因為其他連續的數列都跟 result 相關的數列沒有連起來。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:

        nums = set(nums)

        result = 1
        while nums:
            n = nums.pop()

            left = n
            right = n

            while left - 1 in nums:
                left -= 1
                nums.remove(left)

            while right + 1 in nums:
                right += 1
                nums.remove(right)

            if left <= result <= right:
                result = right + 1
                break

        return result
image 106

也許你也會想看看