Re: [閒聊] 每日leetcode
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
推
06/12 19:08,
1年前
, 1F
06/12 19:08, 1F
推
06/12 19:12,
1年前
, 2F
06/12 19:12, 2F
→
06/12 19:13,
1年前
, 3F
06/12 19:13, 3F
→
06/12 19:13,
1年前
, 4F
06/12 19:13, 4F
→
06/12 19:15,
1年前
, 5F
06/12 19:15, 5F
討論串 (同標題文章)
完整討論串 (本文為第 349 之 1548 篇)：