双指针专题：复写零问题解题思路

双指针专题：复写零问题解析

往期代码参考

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for (int cur = 0, dest = -1; cur < nums.size(); cur++) {
            if (nums[cur]) {
                swap(nums[cur], nums[++dest]);
            }
        }
    }
};

题目背景

题目链接

重点条件：

• 数组长度固定
• 复写零，其他元素往右退（会被挤出去）
• 就地，不能用遍历然后复制的方法

解题思路

异地操作思路

所谓异地操作，就是创建一个新的数组来辅助复写零的操作。我们创建一个与原数组等长的辅助数组来存放复写的元素。

逻辑如下：

1. 判断：cur 指向的元素是否为 0
2. 复写：
   • 非零：复写一次（dest 将 cur 指向的元素复制到辅助数组，dest++，cur++）
   • 零：复写两次（dest 将 cur 指向的元素复制到辅助数组，dest++，再次复制，dest++，cur++）

就地操作优化

题中要求就地操作，直接从前往后进行本地复写操作会造成后续元素被覆盖。因此尝试从后往前复写。

从后向前复写

从后向前复写，肯定是从最后一个被复写元素开始遍历。

使用双指针算法来确定起始位置：

1. 判断 cur 指向元素是否为 0
2. 移动 dest，非零一位，零两位
3. 判断 dest 是否结束
4. cur--

注意：dest 沿用的是异地操作的逆逻辑，且从原始 dest 落尾位置的前一个位置开始复写，起始位置自然也要提前一个，从 -1 开始。

边界处理

用双指针找起始位置时，会有特殊情况：最后一个元素是 0，dest 跑出界了。

这时需要特殊处理：

1. 将 n-1 位置元素写成 0
2. cur--
3. dest -= 2

然后接着之前的逻辑复写就好了。