0283. Move Zeroes

题目信息

题号:

0283

难度:

Easy

主题:

数组、原地修改、稳定顺序

原题:

LeetCode 0283

重点:

所有零移动到末尾、非零元素相对顺序必须保持、不得复制出另一个数组

题目重述

给定整数数组 nums,在原数组上把所有值为 0 的元素移动到末尾,同时保持所有非零元素之间原有的相对顺序。函数没有独立返回数组,调用结束后 nums 本身必须呈现修改结果。

数组长度位于 [1, 10^4],每个元素位于 32 位有符号整数范围。必须原地完成操作,不能通过创建同等规模的数组来保存最终排列。题目的进阶要求是尽量减少对数组元素的写入或交换次数。

自建示例

多个零分散在数组中:

输入:nums = [0, 4, 0, 0, 3, 2]
修改后:nums = [4, 3, 2, 0, 0, 0]
解释:三个非零元素原本按 4、3、2 排列,移动后仍保持这一顺序,三个零全部集中到末尾。

数组中没有零:

输入:nums = [-2, 5, 7]
修改后:nums = [-2, 5, 7]
解释:不存在需要移动的零,数组内容和顺序都保持不变。

稳定压缩非零元素

维护 write,表示下一个应该放置非零元素的位置;read 从左到右扫描数组。 遇到非零值时,把它放到 write,然后递增 write;遇到零时只等待,不改变非零值的先后。

用交换实现原地写回:当 write < read 时,nums[write] 已经是前面留下的零, 交换会把当前非零值放入稳定前缀,并把一个零推到后面;若两指针相等,交换只是自交换。

正确性说明

循环开始时,[0,write) 恰好是已扫描部分的非零元素,且保持原相对顺序; [write,read) 中的元素不影响已确认前缀。读到新的非零值后放入 write,它是扫描顺序中下一个非零值, 不变量继续成立;零不会加入前缀。扫描结束,所有非零元素已经稳定排列在前面,剩余位置只能由零填充。

C++ 实现

class Solution {
public:
    void moveZeroes(std::vector<int>& nums) {
        int write = 0;
        for (int read = 0; read < static_cast<int>(nums.size()); ++read) {
            if (nums[read] == 0) continue;
            std::swap(nums[write], nums[read]);
            ++write;
        }
    }
};

代码分析

两个指针都只向右移动,每个元素最多参与一次判断和一次交换,时间复杂度为 O(n),额外空间为 O(1)。 交换不会改变非零元素的相对顺序;相比先收集非零数组,代码不产生与输入同阶的副本。