0283. Move Zeroes ================= 题目信息 -------- :题号: 0283 :难度: Easy :主题: 数组、原地修改、稳定顺序 :原题: `LeetCode 0283 `_ :重点: 所有零移动到末尾、非零元素相对顺序必须保持、不得复制出另一个数组 题目重述 -------- 给定整数数组 ``nums``,在原数组上把所有值为 ``0`` 的元素移动到末尾,同时保持所有非零元素之间原有的相对顺序。函数没有独立返回数组,调用结束后 ``nums`` 本身必须呈现修改结果。 数组长度位于 ``[1, 10^4]``,每个元素位于 32 位有符号整数范围。必须原地完成操作,不能通过创建同等规模的数组来保存最终排列。题目的进阶要求是尽量减少对数组元素的写入或交换次数。 自建示例 -------- 多个零分散在数组中: .. code-block:: text 输入:nums = [0, 4, 0, 0, 3, 2] 修改后:nums = [4, 3, 2, 0, 0, 0] 解释:三个非零元素原本按 4、3、2 排列,移动后仍保持这一顺序,三个零全部集中到末尾。 数组中没有零: .. code-block:: text 输入:nums = [-2, 5, 7] 修改后:nums = [-2, 5, 7] 解释:不存在需要移动的零,数组内容和顺序都保持不变。 稳定压缩非零元素 ---------------- 维护 ``write``,表示下一个应该放置非零元素的位置;``read`` 从左到右扫描数组。 遇到非零值时,把它放到 ``write``,然后递增 ``write``;遇到零时只等待,不改变非零值的先后。 用交换实现原地写回:当 ``write < read`` 时,``nums[write]`` 已经是前面留下的零, 交换会把当前非零值放入稳定前缀,并把一个零推到后面;若两指针相等,交换只是自交换。 正确性说明 ---------- 循环开始时,``[0,write)`` 恰好是已扫描部分的非零元素,且保持原相对顺序; ``[write,read)`` 中的元素不影响已确认前缀。读到新的非零值后放入 ``write``,它是扫描顺序中下一个非零值, 不变量继续成立;零不会加入前缀。扫描结束,所有非零元素已经稳定排列在前面,剩余位置只能由零填充。 C++ 实现 -------- .. code-block:: cpp class Solution { public: void moveZeroes(std::vector& nums) { int write = 0; for (int read = 0; read < static_cast(nums.size()); ++read) { if (nums[read] == 0) continue; std::swap(nums[write], nums[read]); ++write; } } }; 代码分析 -------- 两个指针都只向右移动,每个元素最多参与一次判断和一次交换,时间复杂度为 ``O(n)``,额外空间为 ``O(1)``。 交换不会改变非零元素的相对顺序;相比先收集非零数组,代码不产生与输入同阶的副本。