题目描述

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

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

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

样例

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

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

注意

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

算法

(双指针) $O(n)$

1. 定义快慢指针，扫描两次数组。
2. 第一次扫描，初始化都为 0，然后根据题意更新快慢指针（不更新数组），直到快指针到达末尾，存储下快慢指针的位置。
3. 从当前快慢指针的位置，开始往回扫描，并更新数组。

时间复杂度

• 扫描数组两次，时间复杂度为 $O(n)$。

空间复杂度

• 原地算法，仅定义了变量，故空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        int i, j;
        i = j = 0;
        while (j < n) {
            if (arr[i] == 0)
                j++;
            i++;
            j++;
        }
        i--; // 将 i 回到最后一次合法的位置。
        j--; // 同理，但 j 有可能仍然等于 n（例如输入为 [0]）。
        while (i >= 0) {
            if (j < n) 
                arr[j] = arr[i];
            if (arr[i] == 0)
                arr[--j] = 0;
            i--;
            j--;
        }
    }
};