LeetCode 41: First Missing Positive - O(n) 時間常數空間解法

問題描述

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

方法一：原地桶排序（置換法）

將每個數 x 放到索引 x-1 的位置（若 1 ≤ x ≤ n）。遍歷數組，對於位置 i，若 A[i] != i+1 且目標位置值不同，交換 A[i] 和 A[A[i]-1]，直到無法交換。最後再次遍歷，第一個 A[i] != i+1 的 i+1 即為答案；全匹配則返回 n+1。

方法二：符號標記法（哈希思想）

第一遍：將非正數替換為 n+2（不可能的值）。
第二遍：對每個值 v = |A[i]|，若 1 ≤ v ≤ n，將 A[v-1] 置為負數（標記 v 存在）。
第三遍：第一個為正數的索引 i，i+1 即為缺失值；全為負則返回 n+1。

代碼對比

方法一邏輯直觀，方法二無交換操作，常數因子更小。兩者均滿足題目約束。

完整代碼（方法二）

class Solution {
public:
    int firstMissingPositive(vector<int>& A) {
        int n = A.size();
        if (n == 0) return 1;
        const int IMPOSSIBLE = n + 2;
        for (int &x : A) if (x <= 0) x = IMPOSSIBLE;
        for (int x : A) {
            int v = abs(x);
            if (v <= n) A[v-1] = -abs(A[v-1]);
        }
        for (int i = 0; i < n; ++i)
            if (A[i] > 0) return i+1;
        return n+1;
    }
};