Re: [閒聊] 每日leetcode

看板Marginalman作者sustainer123 (caster )時間1年前 (2024/06/12 10:09)推噓3(3推 0噓 3→)

留言6則, 5人參與討論串347/1549 (看更多)

※ 引述《yam276 (虛構史學家)》之銘言： : 75. Sort Colors : https://leetcode.com/problems/sort-colors/ : 一個陣列有三種球 : 不准用內建方法不准用新陣列儲存 : 在原本的陣列把球球照種類排序 : 思路: : 三指針 : 左右邊界放指針跟一個中間的遍歷指針 : 每次檢查球球是否需要換位 : 0 => 就換了之後左中+1 : 1 => 不用換中+1繼續 : 2 => 換了之後右-1 中不用動因為下一動會再檢查一次 : 注意 1. while條件是中<=右 : 2. 加一個break判斷避免nums.len()==0 : Code: : impl Solution { : pub fn sort_colors(nums: &mut Vec<i32>) { : let mut left = 0; : let mut mid = 0; : let mut right = nums.len() - 1; : while mid <= right { : match nums[mid] { : 0 => { : nums.swap(left, mid); : left += 1; : mid += 1; : } : 1 => { : mid += 1; : } : 2 => { : nums.swap(mid, right); : if right == 0 { : break; : } : right -= 1; : } : _ => unreachable!(), : } : } : } : } 思路: 其實還是記數不過稍微修改一下只用常數空間+一次遍歷切片應該不算遍歷......吧三指針應該才是正確方法這招就python偷吃步 Python Code: class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ zero = 0 one = 0 two = 0 for n in nums: if n == 0: zero += 1 elif n == 1: one += 1 else: two += 1 nums[:zero] = [0] * zero nums[zero:zero+one] = [1] * one nums[zero+one:] = [2] * two -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.239.169 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718158149.A.30B.html

推

SecondRun

06/12 10:14, 1年前 , 1^F

06/12 10:14, 1^F

→

digua

06/12 10:20, 1年前 , 2^F

06/12 10:20, 2^F

推

argorok

06/12 10:29, 1年前 , 3^F

06/12 10:29, 3^F