題目敘述 Sort Colors
給定一個色彩陣列，裡面的顏色包含0紅色,1白色,2藍色。
要求我們透過in-place操作，把色彩陣列依序從左到右排好，
依序出現的是紅色、白色、藍色。
題目限制不可以使用內建的sort function。
測試範例
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]
約束條件
Constraints:
n == nums.length
n 代表輸入陣列的長度。
1 <= n <= 300
n介於1~300之間。
nums[i]is either0,1, or2.
每個陣列元素的值只有三種可能: 0(紅色), 1(白色), 2(藍色)
.
進階提問
Follow up: Could you come up with a one-pass algorithm using only constant extra space?
能不能想出一次線性掃描，並且只使用常數空間的演算法?
演算法 雙指針 + swap操作
總共只有三個顏色。
根據題意，紅色必須放在左邊那個區域，白色置中，藍色放在右邊那個區域。
可以用雙指針，分別指向頭部(放置紅色的目標區域)和尾部(放置藍色的目標區域)。
遇到紅色就把它放到頭部靠左邊的位置，透過置換元素操作in-place完成。
遇到藍色就把它放到尾巴靠右邊的位置，透過置換元素操作in-place完成。
(實作上的細節是，藍色和尾巴元素交換後，必須多檢查一次，確保間換過來的顏色也是放在正確的區域)
最後留在中間，自然就是的白色。
程式碼 雙指針 + swap操作
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# constant for colors
RED, WHITE, BLUE = 0, 1, 2
# two pointers for RED as well as BLUE
idx_red, idx_blue = 0, len(nums)-1
i = 0
while i <= idx_blue :
if nums[i] == RED:
nums[idx_red], nums[i] = nums[i], nums[idx_red]
# update idx for red
idx_red += 1
elif nums[i] == BLUE:
nums[idx_blue], nums[i] = nums[i], nums[idx_blue]
# update idx for blue
idx_blue -= 1
# i-1 in order to stay and do one more color check on next iteration
i -= 1
# i move forward
i += 1
複雜度分析
時間複雜度: O(n)
從左到右一次線性掃描，每個元素檢查一次，放置到對應的顏色區域。
空間複雜度: O(1)
使用到的都是固定此吋的臨時變數，為常數級別O(1)。
關鍵知識點 指針 + in-place搬移元素的技巧
這題用到的是in-place搬移元素的技巧，
和之前學過的Move Zeros很像，都是鑲在目標區域建立指針，
接著掃描每個元素，把每個元素搬到對應的區域。
