（2）双指针练习：复写零

复写零

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

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

思路解析：

本题有两种思路：

1. 暴力复写
2. 双指针原地复写

• 暴力复写

暴力的方法很简单，因为是复写，所以只需要遇到0先将0位置后面的数据进行挪动覆盖，但是注意要从尾部开始挪动，挪动完毕后在当前位置的下一个位置插入一个数字0，让指针走两步

暴力复写参考代码：

/** @lc app=leetcode.cn id=1089 lang=cpp** [1089] 复写零*/// @lc code=start
// 暴力解法
class Solution
{
public:void duplicateZeros(vector<int> &arr){for (int i = 0; i < arr.size(); i++){if (arr[i] == 0 && arr.size() - 2 > 0){int j = arr.size() - 2;while (j + 1 < arr.size() && j > i){arr[j + 1] = arr[j];j--;}if (i + 1 < arr.size()){arr[++i] = 0;}}}}
};
//  @lc code=end

• 双指针原地复写

对于双指针算法来说，有两种实现方式，第一种是异地复写，即开辟一个新空间，基本思路为遇到非0数字复写一次，遇到数字0复写两次，但是这个算法的空间复杂度为O(N)，所以考虑原地复写

双指针——异地复写参考代码：

/** @lc app=leetcode.cn id=1089 lang=cpp** [1089] 复写零*/// @lc code=start
// 双指针——异地操作
class Solution
{
public:void duplicateZeros(vector<int> &arr){vector<int> ret;ret.resize(arr.size());int cur = 0;int dest = 0;while (dest < ret.size()){if (arr[cur] == 0){dest++;dest++;cur++;}else{ret[dest++] = arr[cur++];}}arr.assign(ret.begin(), ret.end());}
};
//  @lc code=end

原地复写和异地复写的思路是一致的，但是原地复写不可以从源数组的第一个元素开始复写，这样会导致遇到数字0时后面的内容全部都覆盖为0，正确的做法是从最后一个待复写元素开始向最后一个位置进行复写，再依次往前遍历执行复写操作，复写具体操作为：

1. 遇到非0数字向dest位置覆写当前cur位置的数字
2. 遇到0数字向dest位置和dest-1位置复写两个0
3. cur向前移动1步

现在的问题就是如何找到最后一个待复写的元素，可以考虑一次正向遍历，但是在这一次遍历中不进行任何的复写操作，具体操作为：

1. cur所在位置是非0的数字：dest移动一步
2. cur所在位置是数字0：dest移动两步
3. 判断dest是否到最后一个元素的位置
4. cur移动一步

遍历完成后cur所指向的位置即为最后一个待复写的元素，而dest所指向的位置即为最后一个元素的位置，如图所示：

但是此时需要注意一种特殊情况：

当指向的待复写元素是0时，那么此时dest指向的位置已经超出了数组的范围，如果此时在dest位置复写时就会出现越界访问的情况，那么此时需要进行边界修正，修正方法如下：

1. 在dest-1的位置处覆写数字0
2. cur向前走动一步
3. dest向前走动两步

处理完边界情况后就可以进行正常的复写操作过程

双指针——原地复写参考代码：

/** @lc app=leetcode.cn id=1089 lang=cpp** [1089] 复写零*/// @lc code=start
// 双指针——原地操作
class Solution
{
public:void duplicateZeros(vector<int> &arr){int cur = 0, dest = -1;int sz = arr.size();// 找到结果数组中的最后一个重写的元素的位置while (cur < sz){if (arr[cur] == 0){dest += 2;}else{dest++;}if (dest >= sz - 1){break;}cur++;}// 修正边界情况if (dest == sz){arr[dest - 1] = 0;cur--;dest -= 2;}// 覆写while (cur >= 0){if (arr[cur]){arr[dest--] = arr[cur--];}else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};
//  @lc code=end