LeetCode Sort Colors：荷蘭國旗問題 (雙指針/三指針)

問題描述

給定陣列 nums，元素只含 0, 1, 2（分別代表紅、白、藍）。原地排序使相同顏色相鄰，順序為 0, 1, 2。不可使用庫排序函數。進階：單趟掃描、常數空間。

算法一：三指針（紅/白/藍邊界）

維護三個區間：[0, red] 全 0，[red+1, white-1] 全 1，[blue, n-1] 全 2。white 為當前掃描指針。

• 初始 red = -1, white = 0, blue = n。
• 當 white < blue：
  • nums[white] == 0：swap(nums[++red], nums[white++])。
  • nums[white] == 1：white++。
  • nums[white] == 2：swap(nums[white], nums[--blue])（white 不動，需重新檢查換來的元素）。

算法二：兩趟計數排序（簡單直觀）

第一趟計數 cnt[3]，第二趟覆寫陣列。

關鍵代碼 (C++ 三指針單趟)

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int red = -1, white = 0, blue = nums.size();
        while (white < blue) {
            if (nums[white] == 0) {
                swap(nums[++red], nums[white++]);
            } else if (nums[white] == 1) {
                ++white;
            } else { // 2
                swap(nums[white], nums[--blue]);
            }
        }
    }
};

複雜度分析

• 時間 O(n)，單趟掃描。
• 空間 O(1)，原地交換。

總結

Sort Colors 是經典的「荷蘭國旗問題」（Dijkstra 提出）。三指針法將陣列劃分為四區，單趟掃描完成分區，是原地排序、常數空間、線性時間的最優解。面試常考，掌握指針移動邏輯與邊界條件即可。