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)``。
交换不会改变非零元素的相对顺序;相比先收集非零数组,代码不产生与输入同阶的副本。