vvrf / DSA.log

问题拆解

给定数组 nums，要把所有 0 移到末尾，同时保持非零元素原来的相对顺序，而且必须原地修改、不能另开数组。

如果盯着“零”看，很容易想到反复把某个零和后面的元素交换，但这样每个零都可能被搬运多次，操作次数很难控制。换个角度：末尾的零其实不需要我们主动去搬，只要把所有非零元素依次压到数组前部，剩下的位置自然全是零。

与其思考“零该去哪”，不如思考“下一个非零元素该落在哪个下标”。

慢指针记录落点

用 slow 指向下一个非零元素应该存放的位置，fast 负责扫描整个数组。每遇到一个非零元素，就把它交换到 slow 处，然后 slow 前移一格。

public void moveZeroes(int[] nums) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            int tmp = nums[slow];
            nums[slow] = nums[fast];
            nums[fast] = tmp;
            slow++;
        }
    }
}

def moveZeroes(nums):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

func moveZeroes(nums []int) {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != 0 {
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow++
        }
    }
}

pub fn move_zeroes(nums: &mut Vec<i32>) {
    let mut slow = 0;
    for fast in 0..nums.len() {
        if nums[fast] != 0 {
            nums.swap(slow, fast);
            slow += 1;
        }
    }
}

slow 左边（不含 slow）始终是已经排好的非零元素，slow 到 fast 之间则是一段零。当 fast 撞见非零元素时，这次交换恰好用它换回前面那个零，非零元素顺序不会被打乱。

为什么不用担心把已放好的元素换坏？因为当 slow == fast 时交换的是同一个位置，等于什么都没做；只有当中间积压了零，slow 才会落后于 fast，此时换过来的一定是零。

题目要求原地操作，所以函数直接修改 nums、返回 None，不要返回新数组。

复杂度

指标	复杂度	原因
时间	`O(n)`	数组只扫描一遍
空间	`O(1)`	仅用两个下标，原地交换

可以迁移的模式

需要“原地”把满足条件的元素聚拢到一端；
保持相对顺序，不能排序也不能借助额外数组；
用一个慢指针标记“下一个合格元素的落点”，快指针负责发现。

移除元素、按奇偶重排、去掉重复项，都是这个“快慢指针分区”框架的变体。