75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

規則

  1. in-place algorithm (不可用其他資料結構，對原有數據做改變)
  2. 不可用原生 sort 函式

測試案例

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

思路

  1. 用雙指針
  2. 遍歷

實作

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        zero_index = 0 # 左指針
        two_index = len(nums) - 1 # 右指針
        index = 0 # 遍歷指針

        # [2,0,2,1,1,0]
        # 0 <= 5
            # [0, 0, 2, 1, 1, 2], two_index = 4, index = 0
        # 1 <= 4
            # [0, 0, 2, 1, 1, 2], zero_index = 1, index = 1
            # [0, 0, 2, 1, 1, 2], zero_index = 1, index = 2
            # [0, 0, 1, 1, 2, 2], two_index = 3, index = 2
        # 2 <= 3
            # [0, 0, 1, 1, 2, 2], zero_index = 2, index = 3
        # 4 <= 3
            # skip
            # return
        while index <= two_index:
            if nums[index] == 0:
                nums[index], nums[zero_index] = nums[zero_index], nums[index] # 交換
                zero_index += 1
                index += 1
            elif nums[index] == 2:
                nums[index], nums[two_index] = nums[two_index], nums[index] # 交換
                two_index -= 1
            else:
                index += 1
        return nums