双指针算法专题之——复写零

题目介绍

链接: 1089. 复写零

思路分析

那么这道题我们依然可以使用双指针算法来解决

异地复写

先不考虑题目的要求，直接就地在原数组上修改，可能不太好想，我们这里可以先在一个新开的数组上进行复写

起始双指针分别指向两个数组0下标
如果cur指向的元素是非0，dest只把cur的值拷贝下来，无需复写（只有0才复写），然后两者都++

cur如果指向0，那dest要拷贝两次（复写一次），然后两者都++

后续也是如此




其实很简单，就是模拟题目要求的复写操作，非0不动，0复写
对比一下题目的例子，结果是正确的

优化为就地复写

那接下来我们就要尝试在上面的基础上进行优化，优化为原地复写
怎么做呢？现在就只能在原数组上就地操作了

我们来尝试一下：

上来cur指向非0
无需任何操作，两者++即可，刚才我们要拷贝是因为dest指向一个新数组，现在都指向原数组

然后cur是0，所以要复写一次0

那就变成这样了。
这样其实已经不行了，因为2被复写的0覆盖掉了，而cur++之后又指向了刚刚复写的0，这样后面都是0了，肯定的不对的

所以这道题从前向后移动指针是不行的，那我们可以反过来看看！

从后向前呢？

那两个指针都指向最后一个元素吗？
🆗，dest呢从最后一个位置开始，而cur，我们让它一开始指向最后一个被处理的数。
因为最后一个被处理的数处理完毕一定是在数组最后一个位置的。
怎么找最后一个处理的数我们后面说，但是对于当前这个例子，我们知道最后一个处理的数，就是4

然后，就让它们从后往前移动，进行像上面异地复写一样的操作就行了

答案正确！

总结一下：

先找到最后一个被处理的数，然后从后往前进行复写即可

那现在关键问题在于，对于任意一个数组，我们如何找到它最后一个处理的元素是谁？

那么这个问题也可以使用双指针来解决！
怎么做呢？
依然用上面这个例子

让cur从0开始，dest从-1开始，然后，其实就是去模拟整个复写的过程。
如果cur指向的是非0，让dest走一步（只拷贝，不复写），然后cur++；
如果是0，则dest走两步（拷贝+复写），然后cur++
当dest走到最后一个位置时候，就结束了，再走就越界了，此时，cur指向的元素就是最后一个被处理的数。
这个我就不再画图了，大家如果不理解可以自己画一下图走一遍。

但是，还有一种情况需要考虑：

如果最后一个被处理的数是0，这时dest往后走两步有可能出现越界的情况。
所以，针对这种情况，我们可以处理一下：
此时0就是最后一个被处理的数，cur从0开始倒着处理，那此时dest应该拷贝+复写，然后两者都- -
但是此时dest是越界的，即执行拷贝的位置是越界的，所以cur直接- -，然后复写一个0，然后两者都- -。
即把n-1下标置0，cur- -，dest-=2。
后续正常处理就行。

AC代码

上面分析的比较清楚了，代码就不过多解释了

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n = arr.size();// 1.先找到最后一个被处理的元素int cur = 0;int dest = -1;while (dest < n - 1) {if (arr[cur] != 0)dest++;elsedest += 2;if (dest >= n - 1)break; // 如果dest>=n-1（走到最后一个位置或者越界的情况），// 此时cur就是最后一个被处理的元素，不能再++了，直接breakcur++;}// 2.处理一下dest越界的情况if (dest == n) {arr[n - 1] = 0;cur--;dest -= 2;}// 3.从后往前进行复写while (dest >= 0) {if (arr[cur] != 0)arr[dest] = arr[cur];else {arr[dest] = 0;arr[--dest] = 0;}cur--;dest--;}}
};