双指针——复写零

题目链接：1089. 复写零 - 力扣（LeetCode）

题目

算法原理

算法三步曲

第一步：利用双指针，找到修改后最后一个数，即cur扫描，如果扫描的数为0，dest往后走两步，为非0，dest往后走一步。

第二步：处理末尾，dest可能为n，也可能为n-1，如果dest为n，那么修改后的末尾为0。

只需要把末尾修改为0，dest+2即可。

第三步：cur往回走，遇到非0，将dest所指修改为cur所指的数，cur为0，就连续两次修改dest所指的数为0。

代码

void duplicateZeros(int* arr, int arrSize) {
    int dest = -1, cur = 0, n = arrSize;
    while (cur<n)
    {
        if (arr[cur] == 0)
            dest+= 2;
        else
            dest++;
        if (dest >= n - 1)break;
        cur++;
    }//找到需要修改的最后一个数
    if (dest == n)
    {
        arr[n - 1] = 0;
        cur--;
        dest -= 2;
    }//处理末尾
    while (cur >= 0)
    {
        if (arr[cur] == 0)
        {
            arr[dest--] = 0;
            arr[dest--] = 0;
            cur--;
        }
        else
            arr[dest--] = arr[cur--];
    }
}//从后往前赋值

复杂度分析
时间复杂度：O(n) ，其中 n 为数组 arr 的长度，需要遍历两遍数组。
空间复杂度：O(1) ，仅使用常量空间。