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