yicong@algo: ~/code/02-two-pointers/0283-move-zeroes.cpp

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;
}