[LeetCode] #41 First Missing Positive

Problem

給一個數列，找出一個最小的正整數，且該正整數不存在數列中

• Link
• 等級：Hard
• 推薦指數：[⭐⭐⭐⭐] 題目規範 O(n)，需要意識到數列長度是一個可以在 O(n) 取得的資訊，O(2n) 也是算 O(n)。一但長度也是已知資訊，要想出演算法不難，不過要實作出來可能會遇到鬼打牆的狀況，所以還是可以算是一題 Hard 等級的題目

⭐ 有人推薦過的題目的我才會紀錄，所以即使我覺得只有一顆星他依舊是一題有其他人推薦的題目，只是我自己不覺得需要刷
⭐⭐ 代表我覺得有時間再看就好
⭐⭐⭐ 代表可以刷
⭐⭐⭐⭐ 代表一定刷
⭐⭐⭐⭐⭐ 代表多刷幾次甚至把所有 solution 都弄懂

---

想法

題目規範 O(n)，且不要另外 allocate 到與 n 相關的空間
這代表我們要在有走完數列一輪之後就要知道答案，而且不能用一個跟數列等長數列去記憶

可能會有的第一個直覺是 min, max
我們不能直接用 sort 去的到 min/max，因為那會是 O(nlogn)
不過反正有一輪還是終究能統計出 min/max，且只使用 min/max 兩個變數能符合題目的空間要求，所以現在問題就是知道了 min/max 是否就能得出答案？
再進一步想就會發現不行，因為答案樣找的解是有可能是被跳過的那個數，比如數列 [3,4,-1,1]，min 是 -1，max 是 4，但答案是 2，即使我們把 min 定義為 min_positive，min_positive 是 1，max 是 4，也無從得知答案是 2 還是 3

當以上想法行不通，我們會注意到『跳過』是一個關鍵需要被解決的問題，所以我們要想辦法識別出『不連續』

隨便在舉幾個例子就會發現，當數列中沒有出現 1，答案就會是 1，因為 1 就是天然最小正整數
如果有出現 1，那就看有沒有出現 2，如果沒有，那答案就是 2，以此類推

以這個規則，一個長度 5 的數列，能產生的最大可能解就是 6，當數列內容是 [1, 2, 3, 4, 5] 的時候
也就是說，一個長度 5 的數列，我們頂多只會關心 1~5 有沒有出現，當數列中沒有出現 1，答案就會是 1；如果有出現 1，那就看有沒有出現 2，如果沒有，那答案就是 2
我們不關心 -1 有沒有出現，也不關心 7,8,9 有沒有出現，因為那個與最終答案無關

到這裏我們大概就有感覺，可以搭配上 index 來幫忙記憶，因為一個長度 5 的數列，他的 index 是 0-4，符合我們關心的範圍

這裏另外需要意識到『數列長度』是一個可以在 O(n) 取得的資訊，O(2n) 也是算 O(n)，所以即使題目給的 input 是一個典型的 single link list，先走一次來取得 n 的值也是合法的

該怎麼用 index 幫忙記憶？我們可以把數字移動到他應該待的位置上，比如一個長度 5 的數列，如果他有出現 1，那他應該待在 index 0；如果他有出現 3，那他應該待在 index 2
所以我們可以花走一輪的時間就把該歸位的歸位

然後再從頭走一次，第一個遇到的位置上沒有數字的就會是解

比如 [3, 4, -1, 1]，他的長度是 4，所以我們關心 1~4 有沒有出現，透過的方法是：如果 1,2,3,4 有出現，就把他們移到 index 0,1,2,3 來作為記錄方式
我們從 index 0 開始走，首先遇到 3，3 在我們的關心範圍內，且他應該待在 index 2，所以我們把他移到 index 2 去；index 2 原本的數字是 -1，-1 不是我們關心的範圍，所以直接把它覆蓋掉沒差，所以數列變成了 [3, 4, 3, 1]
接著走到 index 1，遇到 4，4 也是在我們的關心範圍內，他應該待在 index 3，所以我們把他移到 index 3 去，index 3 原本的數字是 1，但 1 也是我們關心的範圍，所以 1 也要移走，他應該待在 index 0，所以現在數列變成 [1, 4, 3, 4] （這種連續的 swap 可能會是個實作上的關卡，待會直接看 code 會比較明白其實邏輯不複雜）
接著走到 index 2，值是 3，3 已經待在他該待的位置上，所以不需要做任何事
接著走到 index 3，值到 4，4 也已經待在他該待的位置上，也不需要做任何事

所以現在數列就變成 [1, 4, 3, 4]
我們再從頭走，走到 index 的時候發現，這個位置應該要是 2，但卻出現 4，代表 2 就是一個錯失的數，並且是最小的可能，所以答案就是 2

Source Code (Python)

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        i, length = 0, len(nums)
        while i < length:
            while 0 < nums[i] <= length:
                move_to = nums[i] - 1
                if nums[move_to] == nums[i]: # either move_to==i or there are dup integers
                    break
                nums[i], nums[move_to] = nums[move_to], nums[i]
            i += 1

        for i in range(length):
            if nums[i] != i+1:
                return i+1
        
        return length+1

看一下時間複雜度，裡面有兩個 while，所以感覺起來不是 O(n)
不過我們可以用 swap 過幾次的角度來看第 5 行的 while 到底總共最多做幾次
每一次的 swap，我們都是完成了『將目前處在 i 的位置的數字移到正確的位置上』，而我們總共有多少『正確的位置』，就是 n 個，所以第 9 行的 swap 就是頂多做 n 次