【C++算法】2.双指针_复写零
文章目录
- 题目链接：
- 题目描述：
- 解法-双指针算法
- C++ 算法代码：
- 图解：
题目链接：
1089.复写零
题目描述：
解法-双指针算法
根据“异地操作”优化为“就地操作”。
异地操作是指：原来我们是创立一个新数组，然后设置两个指针
cur和dest。cur指向0的时候，dest复写一次，直到结束。
因为这里不准建立新的数组，只能就地更改，所以是就地操作。
我们要先找到最后一个复写的数。（也可以用双指针算法）
cur指向的位置不是0，那么dest向后移动1位，cur指向的位置是0，那么dest向后移动2位，每次移动后检查dest有没有越界。然后cur++。
但是要注意，上面的算法看似天衣无缝，实际上有问题。
比如：
[1,0,2,3,0,4]变成：
[1,0,0,2,3,0]
cur指向3的时候，dest指向0，然后下一步cur指向0，dest要往后面移动2次。但是这样就越界了。
所以我们要处理一下边界情况。
从后向前完成复写工作。
C++ 算法代码：
class Solution
{
public:void duplicateZeros(vector<int>& arr){// 1. 先找到最后一个数int cur = 0, dest = -1, n = arr.size();//cur指向最后一个数，dest指向最后一个复写的数while(cur < n){if(arr[cur]){//cur不为0，dest移动1步dest++;}else{//cur为0，dest移动2步dest += 2;}if(dest >= n - 1) {//dest到最后或者越界就退出循环break;}cur++;//继续往后找}// 2. 处理一下边界情况if(dest == n){arr[n - 1] = 0;cur--; //cur向前移动1步dest -= 2;//dest向前移动2步}// 3. 从后向前完成复写操作while(cur >= 0){if(arr[cur]){arr[dest--] = arr[cur--];}else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};
图解：
- 开始
- 经过
while循环后
- 这个时候是越界了，执行条件
2
arr[n - 1] = 0;
cur--; //cur向前移动1步
dest -= 2;//dest向前移动2步
- 执行完
2后
cur刚好指向最后一个复写的数，然后执行步骤3。因为arr[cur]不为0，所以arr[dest--] = arr[cur--];
- 因为
arr[cur]不为0，所以arr[dest--] = arr[cur--];
- 因为
arr[cur]为0，所以arr[dest--] = 0;arr[dest--] = 0;cur--;
- 因为
arr[cur]不为0，所以arr[dest--] = arr[cur--];
此时cur<0，不符合循环条件。循环结束。