LeetCode 筆記：Sort Colors（顏色分類 / 荷蘭國旗問題）

三、代碼實現（C++）

class Solution {
public:
    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)
            for (int i = 0; i < cnt[c]; ++i)
                nums[idx++] = c;
    }
};

四、進階：單遍歷三向切分（Dutch National Flag）

維護三個指針：zero 指向下一個 0 的位置，two 指向下一個 2 的位置，i 遍歷。
- nums[i]==0：交換 nums[i++] 和 nums[zero++]
- nums[i]==2：交換 nums[i] 和 nums[two--]（i 不動，需重新檢查換來的值）
- nums[i]==1：i++

void sortColors(vector<int>& nums) {
    int zero = 0, two = nums.size() - 1, i = 0;
    while (i <= two) {
        if (nums[i] == 0) swap(nums[i++], nums[zero++]);
        else if (nums[i] == 2) swap(nums[i], nums[two--]);
        else ++i;
    }
}

五、複雜度分析

• 計數法：時間 O(N)，空間 O(1)
• 三向切分：時間 O(N)，空間 O(1)，單遍歷

本題為荷蘭國旗問題經典變體，三向切分是標準最優解。