75. Sort Colors
給一個array nums
nums裡面的元素指有可能是1、2、3
請將nums由小到大排序好
題目要求in place 且one-pass
思路:
有點像quick sort的思路
用前、中、後指標
用中指標去遍歷整個數組
會有三種情況
(1) 0 : 遇到0就將中指標元素與前指標元素互換，並且兩個都向前1位
(2) 1 : 遇到1就單純讓中指標向前就好
(3) 2 : 遇到2就讓後指標和中指標互換，並且後指標往回1位
當中指標超過後指標跳出迴圈
golang code :
func sortColors(nums []int) {
n:=len(nums)
idx1,idx2,idx3:=-1,0,n
for idx3>idx2{
switch nums[idx2]{
case 0:
idx1++
nums[idx1],nums[idx2]=nums[idx2],nums[idx1]
idx2++
case 1:
idx2++
case 2:
idx3

大師

大師我看到這題第一個念頭是 別騙了 企劃以後一定會加顏色種類

這題加顏色要one pass就不太可能了