75. Sort Colors

題目說明

給定一個數值 array nums，
裡面只有 red, white, blue 三種顏色，需要將陣列排序後，呈現 red -> white -> blue 的順序。
上述三個顏色以數字 0, 1, 2 代表
解這個題目不可以依賴原生的 sort 方法

解題思路

一般的排序演算法最低的 TC 也要 O(NlogN) ，但是這個題目告訴我們只有 0,1,2 這三個數字，因此可以有其他更快的解法來完成，可以達到 TC O(N)

1. Counting Sort
   這個概念比較單純，因為知道我們得陣列裡只有 0,1,2 三個數字，因此掃過一次陣列後，將每個數字的個數存起來，再依次依照個數回填相應的內容即可
2. QuickSort
   用 Partition 的概念可以做到 one-pass (只掃過一次陣列)

• 用 Two pointers , 左指針 L 指向放 0 的位置，右指針 R 指向 放 2 的位置
• 掃過 array 一遍
  • 當遇到 0 就將 current 與 L 交換，L 的位置往後一格，使得 L 前面的數值都會是 0
  • 當遇到 2 則與 R 交換，R 的位置往前一格，使得 R 後面的數值都是 2
• 需注意，當遇到 2 的時候，由於跟 R 交換後的數值，並無法確定是 0, 1, 2 哪一個，因此 current index 仍然會保留在原本位置，在下一個 iteration 才會比對到原本在 R 位置的數值
• 呈上追問，為何遇到 0 並與 L 交換後，current index 就要往前？
  • current index 是由 左至右遍歷，L 指針最多只會跟 current index 重合，不會比 current index 還大，交換後的值只會是 1 或 2，再逐漸遍歷的過程中，會由在 current index 前方或重合的 L 替換掉，因此不會有替換不到的問題

程式碼

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

其他討論

1. 為何 while 條件會是 current <= right，不是 current < right

因為 在當下的 iteration 中，right 指針位置指的是未來的 2 要放的位置，他當前是什麼值並不會知道，還是必須由 current 遍歷到後才能判斷

參考資料

1. NeetCode(2021-06-24)。Sort Colors - Quicksort Partition - Leetcode 75 - Python。摘自 Youtube (2023-01-08)