LeetCode 41 First Missing Positive：原地置換法圖解與代碼

題目重述

同 LeetCode 2890，此處給出更直觀的圖解與另一種寫法。

算法核心：類桶排序，值歸位

遍歷數組，對於每個 nums[i]，若其在 [1, n] 範圍內且不在正確位置（即 nums[nums[i]-1] != nums[i]），則交換至正確位置。重複直到當前位置滿足停止條件。

C++ 代碼（精簡版）

class Solution {
public:
    int firstMissingPositive(vector& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            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;
    }
};

執行過程圖解

圖示展示了 [3,4,-1,1] 如何通過交換變為 [1,-1,3,4]，最終發現索引 1 處值為 -1 ≠ 2，返回 2。

關鍵點總結

1. while 循環：交換後新值需繼續處理
2. 去重條件：nums[nums[i]-1] != nums[i] 避免死循環
3. 範圍限制：只關心 [1, n]，其他值原地停留
4. 時間 O(n)：每個位置最多被交換一次進入正確位置