leetcode 1089. 复写零 | 简单难度

1. 题目详情

给你一个长度固定的整数数组 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. 原题链接

leetcode 1089. 复写零

2. 基础框架

● Cpp代码框架

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {

    }
};

2. 解题思路

1. 题目分析

$(1)$ 本题要求 对数组arr的0元素复写到下一个位置，且其余元素依次后移一位；超过数组长度的元素会被丢弃。
$(2)$ 要求空间复杂度$O(1)$，对数组原地进行操作。

2. 算法原理

$(1)$ 一个好想的思路就是忽略题目对空间复杂度$O(1)$的要求，额外创建一个长度为（假设数组arr长度为n）n的数组nums；遍历arr数组，如果当前元素等于0就2次写入nusm，否则当前元素1次写入nums;直到新数组nums被写满就停止，此时nums中就保存着复写的结果。
$(2)$ 好的，现在让我们尝试不创建额外数组，而是原地修改arr。
使用快慢双指针算法：定义快指针dest，指向复写后的位置；慢指针cur，指向复写前的位置；
$(3)$ 如果直接从前往后进行复写操作，明显是行不通的，因为arr[cur]==0时dest走两步，而cur一直走一步，会出现cur未遍历到的元素被覆盖的情况；
$(4)$ 只能考虑从后往前写。那么如何确定dest和cur的初始位置呢？
首先明确一点，dest一定不慢于cur，故初始的前后位置情况一定是dest与cur相等或dest在cur之后。
完全模拟正着复写0操作，直到cur遍历完整个数组arr，此时dest大概率是处于越界位置的。

只模拟到有效位置：

$(5)$ 处理特殊情况下的越界

$(6)$ 倒着实际执行复写操作
从cur所指位置开始向前遍历：
如果nums[cur]==0，则nums[dest]和nums[dest-1]位置均被设置为0，之后dest-=2；
反之nums[cur]!=0，则nums[dest]位置被设置为nums[cur]的值，之后dest--；
每次判断之后cur都向前移动，即cur--。

3. 时间复杂度

$O(n)$

第一步模拟复写0时，遍历了一遍数组；第三步从cur位置往前复写时也遍历了一遍数组；故时间复杂度是$O(n)$

3. 代码实现

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int dest = -1, cur = 0;
        int n = arr.size();
        // 正着模拟复写，确定最后复写位置
        while(dest < n - 1){
            if(arr[cur] == 0){
                dest+=2;
            }
            else{
                dest++;
            }
            cur++;
        }
        // 循环结束cur指向了最后复写位置的下一个位置，需要回退1
        // dest指向了复写后新数组的最后一个位置
        cur--;
        // 越界控制与调整，此种情况是cur指向0时，dest==n-2，
        // 此时dest模拟复写（dest+=2）后为dest==n，之后循环结束。
        /* 
        特殊处理这种情况：此时是复写0，但只有前1个0有效，后一个0越界了。
        为使下文正常复写，调整复写位置，真正复写时从最后复写位置的前一个位置
        开始，让dest-=2，cur--，并直接对最后复写位置特殊复写
        */
        if(dest >= n){
            dest -= 2;
            cur -= 1;
            arr[n - 1] = 0;
        }
        // 倒着复写
        while(cur >= 0){
            if(arr[cur] == 0){
                arr[dest--] = 0;
                arr[dest--] = 0;
            }
            else arr[dest--] = arr[cur];
            cur--;
        }
    }
};

4. 知识与收获

$(1)$ 有时候正面无法突破问题时，反面是一个很好的突破口。

---

$The$ $End$