LeetCode 筆記：First Missing Positive（缺失的第一個正數）

一、題目描述

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

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

二、解題思路：原地哈希（置換法）

利用數組下標對應正整數：將值為 x (1 ≤ x ≤ n) 的元素放到下標 x-1 處。遍歷數組，對每個位置 i，不斷交換直到：
- 當前元素不在 [1,n] 範圍內，或
- 當前元素已在正確位置（nums[i] == i+1），或
- 目標位置已有相同值（避免死循環）。
最後再次遍歷，第一個 nums[i] != i+1 的位置即為答案，若全滿足則答案為 n+1。

三、代碼實現（C++）

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};

四、複雜度分析

• 時間複雜度：O(n)，每個元素最多被交換一次
• 空間複雜度：O(1)，原地修改

本題核心是「桶排序」思想，將下標作為鍵，值作為值，原地歸位。