yicong@algo:~/code/02-two-pointers$ cat 0283-move-zeroes.cpp
283. 移动零
// 思路
双指针原地交换。slow 指向「下一个非零元素该放的位置」,fast 从头扫到尾; 遇到非零就与 nums[slow] 交换并让 slow 后移,零顺带被挤到后面。
// 时间复杂度
O(n),每个元素只被访问一次
// 空间复杂度
O(1),只用两个下标
// 易错点
要用 swap 而不是直接赋值,否则尾部会残留旧值;题目要求原地修改, 新建数组再写回是 O(n) 空间,不满足进阶要求
// 面试口述要点
slow <= fast 恒成立,写的永远不越过读的位置,所以不会覆盖未读数据; 这个「slow 记录下一个待写位置」的骨架也适用于 27 / 26 / 80 原地删除类题目
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0;
for (int fast = 0; fast < (int)nums.size(); ++fast){
if (nums[fast] != 0){
swap(nums[slow], nums[fast]);
++slow;
}
}
}
};
// 本地测试:输入 n,然后 n 个整数;输出移动后的数组
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<int> nums(n);
for (int& x : nums) cin >> x;
Solution().moveZeroes(nums);
for (size_t i = 0; i < nums.size(); ++i)
cout << nums[i] << (i + 1 == nums.size() ? '\n' : ' ');
return 0;
}