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