LeetCode First Missing Positive 解題詳解：原地哈希 O(n) 時間 O(1) 空間

問題描述

未排序整數數組，找出最小缺失正整數。要求 O(n) 時間、O(1) 額外空間。例如：[1,2,0] → 3，[3,4,-1,1] → 2。

核心思想：原地哈希（桶排序變體）

利用數組下標對應值：理想情況下值 x 應放在下標 x-1。遍歷數組，將每個在 [1, n] 範圍內的值交換到正確位置。最終再次遍歷，第一個 nums[i] != i+1 的下標 i 即為答案 i+1；若全符合則答案 n+1。

交換條件

while (i < n) {
    int x = nums[i];
    if (x > 0 && x <= n && x != i+1 && x != nums[x-1]) {
        swap(nums[i], nums[x-1]);
    } else {
        ++i;
    }
}

• x > 0 && x <= n：只處理有效範圍值。
• x != i+1：已在正確位置無需動。
• x != nums[x-1]：目標位置值相同則說明重複，避免死循環。

完整代碼

int firstMissingPositive(vector& nums) {
    int n = nums.size();
    for (int i=0; i0 && x<=n && x!=i+1 && x!=nums[x-1]) swap(nums[i], nums[x-1]);
        else ++i;
    }
    for (int i=0;i

直觀演示
初始: [3, 4, -1, 1]
i=0: x=3 → swap(nums[0], nums[2]) → [-1, 4, 3, 1]
i=0: x=-1 不符合 → i=1
i=1: x=4 → swap(nums[1], nums[3]) → [-1, 1, 3, 4]
i=1: x=1 → swap(nums[1], nums[0]) → [1, -1, 3, 4]
i=1: x=-1 → i=2
i=2: x=3 正確 → i=3
i=3: x=4 正確 → i=4 結束
檢查: [1, -1, 3, 4] → 下標1值!=2 → 返回 2


複雜度分析

每個元素最多被交換一次到達正確位置，總交換次數 ≤ n，時間 O(n)。
原地修改，額外空間 O(1)。