給定一個(gè)包含紅色、白色和藍(lán)色惩阶，一共 n 個(gè)元素的數(shù)組挎狸，原地對(duì)它們進(jìn)行排序，使得相同顏色的元素相鄰断楷，并按照紅色锨匆、白色、藍(lán)色順序排列冬筒。
此題中恐锣，我們使用整數(shù) 0、 1 和 2 分別表示紅色舞痰、白色和藍(lán)色土榴。
注意:
不能使用代碼庫(kù)中的排序函數(shù)來(lái)解決這道題。
示例:
輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]
進(jìn)階：
一個(gè)直觀的解決方案是使用計(jì)數(shù)排序的兩趟掃描算法响牛。
首先玷禽，迭代計(jì)算出0、1 和 2 元素的個(gè)數(shù)呀打，然后按照0矢赁、1、2的排序贬丛，重寫當(dāng)前數(shù)組撩银。
你能想出一個(gè)僅使用常數(shù)空間的一趟掃描算法嗎？
思路解析
設(shè)置left豺憔，right额获，cur指針
判斷cur指針是0，則與left代表的數(shù)值進(jìn)行交換恭应，兩者索引都加1
若是2抄邀，則和right代表的數(shù)值進(jìn)行交換，right-1昼榛，但是cur不動(dòng)撤摸，因?yàn)楹竺娴脑夭恢朗欠袷呛畏N情況，需要繼續(xù)判斷褒纲。left指針一定指向的0准夷，交換后沒(méi)有問(wèn)題，所以累加
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums or len(nums) == 0:
return []
left = 0
right = len(nums) - 1
cur = 0
while cur <= right:
if nums[cur] == 0:
nums[left], nums[cur] = nums[cur], nums[left]
left += 1
cur += 1
elif nums[cur] == 2:
nums[right], nums[cur] = nums[cur], nums[right]
right -= 1
else:
cur += 1
AC75
