題目出處

75. Sort Colors

難度

medium

個人範例程式碼

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # only 0, 1, 2
        self.partition(nums, 2, 0, len(nums)-1)
        return 


    def partition(self, nums, pivot, start, end):
        if pivot == 0:
            return 

        left, right = start, end

        while(left <= right):
            while(left <= right and nums[left] < pivot): # 0, 1
                left += 1
            while(left <= right and nums[right] >= pivot): # 2
                right -= 1
            if(left <= right):
                nums[left], nums[right] = nums[right], nums[left]
                # check twice
                # left += 1
                # right -= 1
        else: # after left and right cross, all 0, 1 will be left, 2 will be right
            # start, right(0, 1), left(2), end            
            # start, right(0), left(1), end

            self.partition(nums, pivot-1, 0, right)

算法說明

此題是考 partition 的延伸題，也可以單純使用三指標來快速解掉，
不過之後還有一題多顏色的題目，基本上 partition 還是要會解。

這題會經常錯在遞迴判斷式與邊界條件，導致無法 AC。

遞迴判斷式

遞迴的定義

while(left <= right):
    while(left <= right and nums[left] < pivot): # 0, 1
        left += 1
    while(left <= right and nums[right] >= pivot): # 2
        right -= 1
    if(left <= right):
        nums[left], nums[right] = nums[right], nums[left]

遞迴的拆解

這邊要處理的是邊界問題，往前我們還需要多注意 while(left <= right)，
這會導致我們是「交錯」才結束，

結束時的狀態為 「start < right < left < end」，由於與 pivot 相等的在兩側都有可能出現，
拆解的搜尋條件為

• start ~ right
• left ~ end

這題本身較簡單，但其實不需要拆到那麼複雜，
但為了後續的 partition 題目方便，這裡就先用最泛用的方式解

self.partition(nums, pivot-1, 0, right)

遞迴的中止

如果 pivot = 0，return

一樣也是因為這題題目相對單純，因此我們可以這樣寫死。

input handling

這題沒有特別說要怎麼處理特殊的 input，預設的 input 都給正確的。

Boundary conditions

上方已經說明完囉

Reference

• 颜色分类 · Sort Colors