LeetCode 75 顏色分類：荷蘭國旗問題的三種解法全解析

題目回顧

給定包含 0（紅）、1（白）、2（藍）的數組，原地排序使相同顏色相鄰，順序為 0, 1, 2。不可使用庫排序函數。

解法一：計數排序（兩遍掃描，O(n) 時間，O(1) 空間）

統計 0, 1, 2 的個數，然後覆寫數組。

void sortColors(vector<int>& nums) {
    int cnt[3] = {0};
    for (int x : nums) cnt[x]++;
    int idx = 0;
    for (int c = 0; c < 3; ++c)
        while (cnt[c]--) nums[idx++] = c;
}

簡單直觀，但需要兩遍掃描。

解法二：單遍掃描 + 三指針（荷蘭國旗算法，一遍過）

維護三個區間：
[0, p0) 全 0  |  [p0, i) 全 1  |  (p2, n-1] 全 2  |  [i, p2] 待處理

void sortColors(vector<int>& nums) {
    int p0 = 0, p2 = nums.size() - 1, i = 0;
    while (i <= p2) {
        if (nums[i] == 0) swap(nums[i++], nums[p0++]);
        else if (nums[i] == 2) swap(nums[i], nums[p2--]);  // i 不動，換來的需再檢查
        else ++i;  // nums[i] == 1
    }
}

關鍵點：遇到 2 交換後 i 不遞增，因為換來的元素可能是 0 或 1，需重新判斷。

解法三：從後向前的雙指針（原文思路，同樣一遍過）

維護 e0（最後一個 0 的位置）、e1（最後一個 1 的位置），從右向左遍歷：

void sortColors(int A[], int n) {
    int e0 = n-1, e1 = n-1;
    for (int i = n-1; i >= 0; --i) {
        if (A[i] == 1) swap(A[i], A[e0--]);
        else if (A[i] == 2) {
            swap(A[i], A[e0]);
            swap(A[e0], A[e1--]);
            e0--;
        }
    }
}

邏輯等價於正向三指針，只是視角不同。

複雜度總結

面試加分項

• 能說清三指針不變量（Loop Invariant）。
• 能推廣到 k 種顏色（計數排序 O(n+k)，多指針 O(nk)）。
• 討論穩定性：本題不要求穩定，若要求穩定需額外空間。