※ 引述《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