【算法学习】二、移动零（Rust 解法）

题目描述

给定一个整数数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

限制条件

• 必须原地操作，不得使用额外的数组。
• 保持非零元素的相对顺序。
• 最小化操作次数。

---

示例

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

---

初始解法（remove + push）

struct Solution;

impl Solution {
    pub fn move_zeroes(nums: &mut Vec<i32>) {
        let mut i = 0;
        let mut zero_count = 0;

        while i < nums.len() {
            if nums[i] == 0 {
                zero_count += 1;
                nums.remove(i);  // O(n) 操作，非常耗性能
            } else {
                i += 1;
            }
        }

        for _i in 0..zero_count {
            nums.push(0);
        }
    }
}

fn main() {
    let mut list = vec![0, 0, 0, 0, 0, 1, 2, 0, 3, 0, 4, 5, 0, 6, 7, 8, 0, 9];
    Solution::move_zeroes(&mut list);
    println!("{:?}", list)
}

问题：

• remove(i) 是线性时间复杂度（O(n)），每次都会移动整个后缀数组。
• 多次调用 remove 导致整体性能极差，时间复杂度退化为 O(n²)。
• 实测大数组下性能很差，几乎不可用。

---

改进解法：双指针 + 原地交换

struct Solution;

impl Solution {
    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);  // 非 0 移到前面
                slow += 1;
            }
        }
    }
}

fn main() {
    let mut list = vec![0, 0, 0, 0, 0, 1, 2, 0, 3, 0, 4, 5, 0, 6, 7, 8, 0, 9];
    Solution::move_zeroes(&mut list);
    println!("{:?}", list)
}

作用方式

slow 会一直停在前面，等着 fast 找到非零的数。一旦找到了，就把它俩交换，把非零数往前搬。比如第一次遇到非零数时，slow = 0，fast = N，交换之后，非零数就被放到了最前面，然后 slow 向前一步，fast 继续扫后面的数。

---

Rust 额外知识点

所有权 & 借用

在同一作用域中同时只能存在：一个可变引用 或 一个/多个不可变借用

在 Rust 中，每个值都有一个所有者（owner），一个值在同一时刻只能被一个可变引用或多个不可变引用借用。

pub fn move_zeroes(nums: &mut Vec<i32>) // 可变引用 &mut Vec

• &mut：表示你拿的是 nums 的 可变引用。
• 你只能有一个 &mut 引用同时存在，否则 Rust 会报错。

---

为什么不能边遍历边 remove？

最开始的写法：

for (index, &num) in nums.iter().enumerate() {
    if num == 0 {
        nums.remove(index);
    }
}

❌ 错在：nums.iter().enumerate() 返回的是 &num（不可变借用），但 remove 需要修改 nums（需要可变借用）！

Rust 不允许同一作用域同时存在 &nums 和 &mut nums，因为这可能导致数据竞争或内存错误。