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

題目描述

給定一個未排序的整數陣列，找出其中沒有出現的最小正整數。要求時間複雜度 O(n) 且僅使用常數額外空間。

• 輸入 [1,2,0] → 輸出 3
• 輸入 [3,4,-1,1] → 輸出 2

解題思路分析

思路 1：排序後掃描（O(n log n)）

先對陣列排序，再線性掃描找第一個缺失的正整數。雖然簡單，但不滿足 O(n) 時間要求。

思路 2：桶排序 / 原地哈希（O(n) 時間，O(1) 空間）

核心觀察：對於長度為 n 的陣列，第一個缺失的正整數必然在 [1, n+1] 區間內。大於 n 的數字不可能是答案，可以忽略。

我們可以將陣列視為 n 個「桶」，第 i 個桶（索引 i-1）應該存放數值 i。通過交換操作，將每個在 [1, n] 範圍內的數字放到其對應的位置上。最終再掃描一次陣列，第一個 A[i] != i+1 的位置即為答案。

程式碼實現

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        bucket_sort(A, n);
        for (int i = 0; i < n; ++i)
            if (A[i] != i + 1) return i + 1;
        return n + 1;
    }

private:
    void bucket_sort(int A[], int n) {
        for (int i = 0; i < n; ++i) {
            // 將 A[i] 放到正確位置：值為 x 應放在索引 x-1
            while (A[i] != i + 1) {
                // 不符合條件則跳出：非正數、超出範圍、或目標位置已有相同值（避免死循環）
                if (A[i] <= 0 || A[i] > n || A[i] == A[A[i] - 1]) break;
                swap(A[i], A[A[i] - 1]);
            }
        }
    }
};

關鍵點解析

1. 原地交換：利用陣列本身作為哈希表，無需額外空間。
2. while 迴圈而非 if：交換後新換來的 A[i] 可能仍需繼續放置，故用 while。
3. 終止條件：
   • A[i] <= 0 || A[i] > n：不在關注範圍內。
   • A[i] == A[A[i]-1]：目標位置已有正確值（或重複值），交換無意義，防止無限循環。
4. 時間複雜度證明：每次交換都能將至少一個數字放到最終正確位置，總交換次數 ≤ n，故總體 O(n)。

總結

這是一道經典的「原地哈希」技巧題目，核心在於將「索引」與「值」建立映射關係，巧妙滿足了嚴苛的時空間限制。