LeetCode First Missing Positive：原地哈希桶排序思想找最小缺失正整數

題目回顧

給定未排序整數數組 nums，找出其中缺失的最小正整數。要求：O(n) 時間、O(1) 額外空間。

例子：[1,2,0] → 3；[3,4,-1,1] → 2

核心洞察：索引即值，值歸位

對於長度為 n 的數組，最小缺失正整數必在 [1, n+1] 範圍內。我們可以嘗試將每個正整數 x ∈ [1, n] 放到索引 x-1 的位置上。最終遍歷數組，第一個 nums[i] != i+1 的位置 i，答案即為 i+1；若全滿足，答案為 n+1。

原地交換算法（桶排序變體）

class Solution {
public:
    int firstMissingPositive(vector& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            // 將 nums[i] 放到正確位置，直到：
            // 1. 超出範圍 [1,n]
            // 2. 目標位置已有正確值（避免死循環處理重複值）
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[nums[i] - 1], nums[i]);
            }
        }
        // 掃描找第一個不匹配的位置
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};

關鍵細節解析

1. while 而非 if：交換後 nums[i] 換來新值，需繼續處理，直到滿足停止條件
2. 去重判斷：nums[nums[i]-1] != nums[i] 防止重複值導致無限循環（如 [1,1]）
3. 範圍過濾：只處理 [1, n] 內的值，負數、0、>n 的值直接忽略，它們不影響答案
4. 時間複雜度證明：每次 swap 至少將一個數字放到正確位置，每個位置最多被放置一次，總 swap 次數 ≤ n，故 O(n)

Python 版本

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        while i < n:
            cur = nums[i]
            if 1 <= cur <= n and nums[cur - 1] != cur:
                nums[cur - 1], nums[i] = nums[i], nums[cur - 1]
            else:
                i += 1
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

測試用例

assert Solution().firstMissingPositive([1,2,0]) == 3
assert Solution().firstMissingPositive([3,4,-1,1]) == 2
assert Solution().firstMissingPositive([7,8,9,11,12]) == 1
assert Solution().firstMissingPositive([1,2,3]) == 4
assert Solution().firstMissingPositive([1,1]) == 2

總結

此題是「原地哈希 / 索引映射」技巧的經典應用：

• 利用數組下標作為隱式哈希鍵
• 通過交換實現「值歸位」
• 在 O(1) 空間下達到 O(n) 時間

同類思想還適用於：找重複數、找所有缺失數、數組去重 等問題。