LeetCode1089. 复写零

题目描述

本题目来自LeetCode上的『1089. 复写零』

给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。

要求：请对输入的数组就地进行上述修改，不要从函数返回任何东西。

示例1：

输入：[1,0,2,3,0,4,5,0]
输出：null
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

提示

1 <= arr.length <= 10000
0 <= arr[i] <= 9

题解

本题要求原地修改，因此不能重新开个数组。

原地修改，常用的方式是将数组 从后往前 覆盖，下一步就需要确定修改后的数组的末尾的值是哪一个。采用双指针的方法，设快慢指针分别为 fast = 0 和 slow = 0，默认步长都为 $1$，若 arr[slow] == 0，则 fast += 2。这样，当快指针遍历结束后，slow 指向的位置是所要求的位置的下一位（可以在纸上画一下）。

再采用双指针的方法，从后往前修改数组，遇到 $0$，就再向前写一个 $0$。

细节： 若跳出循环的时候 fast == n + 1，说明修改后的数组的末尾的值正好是 $0$，这个 $0$ 复写后的 $0$ 应该位于 arr[n] 的位置，但这超出了范围，因此此种情况需要特判。

代码

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        int fast = 0, slow = 0;
        while (fast < n) {
            fast += arr[slow] == 0 ? 2 : 1;
            ++slow;
        }
        int i = n - 1, j = slow - 1;
        if (fast == n + 1) {
            arr[i--] = 0;
            --j;
        }
        while (i >= 0) {
            arr[i--] = arr[j];
            if (arr[j] == 0 && i >= 0) {
                arr[i--] = 0;
            }
            --j;
        }
    }
};