推 Smallsh: 大師 06/12 19:08
推 SecondRun: 大師 06/12 19:12
→ SecondRun: 我看到這題第一個念頭是 別騙了 企劃以後一定會加顏色 06/12 19:13
→ SecondRun: 種類 06/12 19:13
→ JIWP: 這題加顏色要one pass就不太可能了 06/12 19:15
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--
nums[idx2],nums[idx3]=nums[idx3],nums[idx2]
}
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.103.4 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718190508.A.F9E.html