题目描述

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

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1：

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

示例 2：

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

提示：

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

算法原理

首先我们通常都会考虑从头开始复写，但是看一下这样一个示例：
[1,0,2,3,0,4,5,0]
复写过程是：
1
100 注意此时2已经被覆盖了，因此需要临时变量记录2
1002 临时变量改为记录3
10023 临时变量改为记录0
1002300 很好这下一下子覆盖了45，又需要增加一个临时变量了
10023004

根据上面的步骤我们发现每当复写一个0，就需要增加一个临时变量。这就不是本地操作了，而是要增加一个数组来存储被覆盖的数值了。

所以考虑逆向思维，我们从数组尾部开始开始复写，譬如上例
我们在已经知道结果是
[1,0,0,2,3,0,0,4]的前提下，是不是可以从4开始
步骤变成了：
[1,0,2,3,0,cur(4),5,dest]
开始
[1,0,2,3,cur(0),4,dest,4]
[1,0,2,cur(3),dest,0,0,4]
[1,0,cur(2),dest,3,0,0,4]
[1,cur(0),dest,2,3,0,0,4]
[cur(1)、dest,0,0,2,3,0,0,4]
[1,0,0,2,3,0,0,4]
可以看到我们只需要将cur指针指向数值交给dest拷贝，就无需临时变量存储数据。

所以现在问题转化为如何找到复写后的数组最后一位在原数组的索引，这时候就要用上快慢指针的解法。
cur、dest从左向右遍历
cur指向非零元素，cur和dest向右移动一步
cur指向零元素，cur向右移动一步，dest向右移动两步。
当dest指向数组最后一位元素或数组最后一位元素的后一位，就停止。
（也就是要注意dest会有越界风险）

算法实现

class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        int dest = 0, cur = 0;
        //找到复写最后一个位置
        for (; dest < arr.size(); cur++,dest++)
        {
            if (!arr[cur])
                dest++;
        }
        --cur;
        --dest;
        //处理边界情况
        if (dest == arr.size())
        {
            arr[--dest] = 0;
            --dest;
            --cur;
        }
        //开始复写
        while (cur >= 0)
        {
            if (!arr[cur])
            {
               arr[--dest]= arr[dest] = 0;
            }
            else
            {
                arr[dest] = arr[cur];
            }
            --dest;
            --cur;
        }
    }
};