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