LeetCode 75 詳解：Sort Colors (顏色排序/荷蘭國旗問題)

題目描述

給定包含 0、1、2 的陣列，原地排序使相同顏色相鄰，順序為 0（紅）、1（白）、2（藍）。即荷蘭國旗問題。

範例：[2,0,2,1,1,0] → [0,0,1,1,2,2]

解法對比

解法 1：計數排序（兩遍掃描，最簡單）

void sortColors(vector& 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;
}

• 時間 O(n)，空間 O(1)
• 兩遍掃描：統計 + 重寫

解法 2：單遍掃描三指針（標準荷蘭國旗算法）

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

void sortColors(vector& nums) {
    int p0 = 0, p2 = nums.size() - 1, i = 0;
    while (i <= p2) {
        if (nums[i] == 0) {
            swap(nums[i++], nums[p0++]);  // 0 交換到左區，i/p0 後移
        } else if (nums[i] == 2) {
            swap(nums[i], nums[p2--]);    // 2 交換到右區，p2 前移，i 不動（新換來的需檢查）
        } else {
            ++i;  // 1 保持中間，i 後移
        }
    }
}

解法 3：原文 range-for 版本（簡潔但非原地、額外空間）

void sortColors(vector& nums) {
    vector v0, v1, v2;
    for (int n : nums) {
        if (n == 0) v0.push_back(0);
        else if (n == 1) v1.push_back(1);
        else v2.push_back(2);
    }
    nums.clear();
    nums.insert(nums.end(), v0.begin(), v0.end());
    nums.insert(nums.end(), v1.begin(), v1.end());
    nums.insert(nums.end(), v2.begin(), v2.end());
}

三指針算法圖解

nums = [2,0,2,1,1,0]

複雜度分析

關鍵點總結

1. 三指針不變量：循環保持四區間性質，是荷蘭國旗問題標準解
2. 交換 2 時 i 不動：換來的元素可能是 0 或 1，需重新檢查
3. 擴展性：k 顏色排序可用計數排序 O(n+k) 或多指針推廣
4. 面試首選：單遍三指針展示算法功力，計數排序作為備選說明

總結

LeetCode 75 是經典荷蘭國旗問題。三指針單遍掃描為最優解法，時間 O(n)、空間 O(1)、原地排序。計數排序代碼更簡潔，兩遍掃描工程上可接受。range-for 版本雖直觀但需額外空間，不符合原地要求。掌握三指針不變量設計是解決分區類問題的核心技能。