LeetCode 筆記 - 41. First Missing Positive

Posted on

題目在此 41. First Missing Positive

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

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

解題思維

這題的難點就在於怎麼在 O(n) 的時間複雜度內解決。
既然都跟你說 O(n) 了，那就不能用排序了，因為以現在時代的極限，排序的時間複雜度最快也是 O(nlogn)。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

也許你也會想看看