个人主页:Lei宝啊
愿所有美好如期而遇
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/duplicate-zeros/
算法原理
双指针法,不一定是说就要使用指针,只是一种形象的说法,在数组中,我们一般将数组下标当做指针,这道题目我们仍然定义cur以及dest,当我们将cur和dest都定义在数组开始时,按照逻辑执行下去,那么遇到0时,后面的部分值会被覆盖,所以我们不能从左向右走,而是从右向左走,但是这样的话我们又怎么知道cur和dest的位置呢?我们看图示
图示
正常从左向右走,图示:
2就被覆盖了,但是我们先走下去(不考虑覆盖),看看cur和dest的最终位置:
当dest到达右边界时停止。
也就是说,我们可以先遍历找到指针位置,再倒过来复写,图示:
我们还有一种特殊情况,就是dest越过边界,到了size,那么我们就要先将数组下标为size-1的位置置0,因为size位置不能置0,是越界的,然后我们dest -= 2,cur--,接下来正常走就好。
代码
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
int cur = 0;
int dest = -1;
int n = arr.size();
while(cur < n)
{
if(arr[cur] != 0)
{
dest++;
}
else
{
dest += 2;
}
if(dest >= n - 1)
{
break;
}
cur++;
}
if(dest > n - 1)
{
arr[n - 1] = 0;
dest -= 2;
cur--;
}
while(cur >= 0)
{
if(arr[cur] != 0)
{
arr[dest--] = arr[cur--];
}
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};