LeetCode 顏色分類：荷蘭國旗問題三路快排分區

題目描述

給定包含 0（紅）、1（白）、2（藍）的數組，原地排序使相同顏色相鄰，且按紅、白、藍順序排列。要求單次遍歷、O(1) 空間。

範例：

輸入: [1, 2, 1, 2, 0, 2, 1, 0, 2, 0, 0, 2]
輸出: [0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 2]

解題思路：三指針單次遍歷

擴展「兩顏色雙指針」思想，維護三個區域：

• [0, left)：已排好的 0（紅）
• [left, mid)：已排好的 1（白）
• (right, end]：已排好的 2（藍）
• [mid, right]：待處理區域

遍歷邏輯：

1. nums[mid] == 0：與 left 交換，left++、mid++（換來的必是 1，因已掃描過）
2. nums[mid] == 1：mid++
3. nums[mid] == 2：與 right 交換，right--（mid 不動，換來的值未知需再判斷）

時間複雜度：O(n)，空間複雜度：O(1)。

Python 參考實現

class Solution:
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        left = mid = 0
        right = len(nums) - 1
        
        while mid <= right:
            if nums[mid] == 0:
                nums[mid], nums[left] = nums[left], nums[mid]
                left += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:  # nums[mid] == 2
                nums[mid], nums[right] = nums[right], nums[mid]
                right -= 1

# 測試
if __name__ == "__main__":
    sol = Solution()
    nums = [1, 2, 1, 2, 0, 2, 1, 0, 2, 0, 0, 2]
    sol.sortColors(nums)
    assert nums == [0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 2]
    print("測試通過：", nums)

核心要點總結

• 三路分區：快速排序 partition 的三路變體（Dijkstra 提出）
• 指針不變量：left、mid、right 精確劃分四區域
• 關鍵細節：交換 2 時 mid 不前進，因換來的元素未經檢查
• 泛化應用：可擴展到 K 個顏色（計數排序）或任意 pivot 的三路快排

荷蘭國旗問題是原地排序的經典教學案例，掌握「三指針不變量」設計思想，對理解分治算法極有幫助。