双指针算法实战：移动零与复写零解析

复杂度分析

• 空间复杂度：O(1)，只使用了有限的额外空间。
• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历一次数组。

复写零

题目链接：【力扣】Duplicate Zeros 题目描述：给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。注意：不要在超过该数组长度的位置写入元素。

示例： 输入：arr = {1,0,2,3,0,4,5,0} 输出：{1,0,0,2,3,0,0,4}

解题思路

同样可以使用双指针法来解决这个问题。一个指针 cur 用于遍历数组，另一个指针 dest 用于指向复写零后数组中元素应该放置的位置。当遇到零元素时，将 dest 指针后的元素依次向后移动两位，并在 dest 和 dest+1 的位置都放置零。当遇到非零元素时，将其放置在 dest 指针所指的位置，并将 dest 指针向后移动一位。

为什么从右往左？

这个解题思路是怎么来的呢？如果我们尝试从左往右遍历，当 arr[cur] != 0 时，让 arr[dest] = arr[cur]，然后 cur--, dest--；当 arr[cur] == 0 时，让 arr[dest--] = 0, arr[dest--] = 0, cur--。这样遍历没有问题，因此我们选择从右往左遍历。所以我们只要找到最后要'复写'的数即可。

首先我们从左往右遍历数组，确定 dest 的最终位置。当 arr[cur] != 0 时，我们让 dest 的后面一个的值赋予 arr[cur] 正指向的那个值；当 arr[cur] == 0 时，我们让 dest 的后两个值都赋予 0。当走到这一步时，cur 找不到下一个为 2 的值了，因此我们不能简单地从左往右遍。

我们需要找最后一个要复写的数。起初让 cur 指向数组的开头，dest 指向 -1 的位置。

代码实现（以 C++ 为例）

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        // dest 用于标记复制零元素后的新位置，初始值为 -1
        int dest = -1;
        // cur 用于遍历原始数组，初始值为 0
        int cur = 0;
        int n = arr.size();
        // 遍历原始数组，确定复制零元素后的新位置
        while (cur < n) {
            // 如果当前元素不为 0
            if (arr[cur] != 0) {
                // dest 向后移动一位
                dest++;
            } else {
                // 如果当前元素为 0，dest 向后移动两位（因为要复制一个零）
                dest += 2;
            }
            // 如果 dest 已经到达或超过新数组的最后一个位置，跳出循环
            if (dest >= n - 1) break;
            // cur 向后移动一位，继续遍历原始数组
            cur++;
        }
        // 如果 dest 正好等于新数组的长度
        if (dest == n) {
            // 将新数组的最后一个位置设为 0
            arr[n - 1] = 0;
            // dest 回退两位
            dest -= 2;
            // cur 回退一位，因为上一步 cur 多走了一步
            cur--;
        }
        // 从后往前遍历原始数组，进行复制操作
        while (cur >= 0) {
            // 如果当前元素不为 0
            if (arr[cur] != 0) {
                // 将当前元素复制到新位置
                arr[dest] = arr[cur];
                // cur 和 dest 都向前移动一位
                cur--;
                dest--;
            } else {
                // 如果当前元素为 0，先将 0 复制到 dest 位置，再将另一个 0 复制到 dest - 1 位置
                arr[dest--] = 0;
                arr[dest--] = 0;
                // cur 向前移动一位
                cur--;
            }
        }
    }
};

复杂度分析

• 空间复杂度：O(1)，只使用了有限的额外空间。
• 时间复杂度：O(n)，其中 n 是数组的长度。我们需要遍历两次数组。

总结

通过这两道题目，我们可以看到双指针算法在处理数组相关问题时的高效性和灵活性。希望大家在今后的算法学习中，能够熟练掌握双指针技巧，解决更多复杂的问题。