Re: [閒聊] 每日leetcode已回收
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
推
06/12 10:03,
1年前
, 1F
06/12 10:03, 1F
推
06/12 10:04,
1年前
, 2F
06/12 10:04, 2F
→
06/12 10:12,
1年前
, 3F
06/12 10:12, 3F
→
06/12 10:19,
1年前
, 4F
06/12 10:19, 4F
推
06/12 11:00,
1年前
, 5F
06/12 11:00, 5F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 346 之 1549 篇)：