0283. Move Zeroes¶
题目信息¶
- 题号:
0283
- 难度:
Easy
- 主题:
数组、原地修改、稳定顺序
- 原题:
- 重点:
所有零移动到末尾、非零元素相对顺序必须保持、不得复制出另一个数组
题目重述¶
给定整数数组 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)。
交换不会改变非零元素的相对顺序;相比先收集非零数组,代码不产生与输入同阶的副本。