算法---双指针练习-2（复写零）

本文主要是介绍算法---双指针练习-2（复写零），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目解析

题目地址：点这里

在这里插入图片描述

2. 讲解算法原理

在这里插入图片描述

首先，通过遍历数组 arr 来确定复写后数组的最后一个元素的值下标 dest。这个下标表示在复写后的数组中，最后一个元素应该存储的位置。遍历过程中，如果遇到非零元素，则 dest 增加 1；如果遇到零元素，则 dest 增加 2。这样做的目的是为了计算出复写后数组的长度。

接下来，检查特殊情况。如果 dest 的值等于原始数组 arr 的长度 n，说明原始数组最后一个元素是零，而复写后的数组长度没有增加。在这种情况下，需要手动将复写后数组的最后一个元素设置为零，并适当调整 dest 和 cur 的值。

然后，通过从后向前的方式遍历数组 arr，从 dest 的位置开始填充复写后的数组。具体操作如下：
1.如果当前元素不是零，则将其复制到位置 dest，然后将 dest 减1。
2.如果当前元素是零，则需要复制两个零元素到位置 dest 和 dest-1。如果 cur 等于 dest，说明已经复制了所有的零元素，此时只需将 dest 减1；否则，将 dest 减2，并将两个零元素复制到相应位置。

这样，经过循环遍历后，原始数组 arr 中的零元素会被复制并移动到复写后数组的相应位置，从而实现了零元素的复写。最终，原始数组 arr 中的其他元素和复写后数组的前部分元素会保持相同。

3. 编写代码

void duplicateZeros(vector<int>& arr) {int n=arr.size();//查找复写后数组最后一个元素的值下标int dest=-1;int cur=0;while(dest<n){if(arr[cur]) dest++;else dest+=2;if(dest>=n-1) break;cur++;}//处理特殊情况if(dest==n){arr[n-1]=0;dest-=2;cur--;}while(dest>0){if(arr[cur]!=0){arr[dest]=arr[cur];dest--;}else if(arr[cur]==0 ){if(cur==dest){dest--;}else{arr[dest--]=0;arr[dest--]=0;}}cur--;}}