推 SecondRun: 別捲了 06/12 10:14
→ digua: 大師 06/12 10:20
推 argorok: 大師 06/12 10:29
推 SecondRun: 最後三行我C#要展開成一串 哭啊 06/12 10:34
→ sustainer123: 語法糖 python就是貼心 06/12 10:36
→ Rushia: 不算吧 切片要重新創一個陣列複製值 06/12 11:36
※ 引述《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