专题一 - 双指针 - leetcode 1089. 复写零 - 简单难度

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$