Re: [閒聊] 每日leetcode

[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!(),
            }
        }
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.48.97 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718157776.A.C1C.html
推 SecondRun: 大師
推 DJYOSHITAKA: 別再捲了
→ sustainer123: 大師
→ digua: 大師
推 CanIndulgeMe: 大師