思路:双指针法
1.因为是就地修改不能用新数组,但可以试试看看结果是什么(结尾数是4)
(cur遍历数组)(当cur!=0时替换一个 当cur==0 时替换两个)
2.从前到后会覆盖所以不行
3.试试从后往前
因为用两个数组看出修改后数组最后一个元素为4,所以可以从后往前试试,结果发现可以哎!
所以现在问题是如何找出修改后的数组最后的数字在原数组的位置。
4.找出它的位置? ? ?(思路是由上面1用两个数组实践来的)
????????依旧是双指针法
????????1.判断cur位置的值
????????2.dest根据cur走一步或两步
????????3.判断dest是否到数组末尾(到了的话,此时cur所指元素就是要找的末尾元素)
? ? ? ? 4.cur++
4.5边界情况
有可能dest因为cur最后走两步走到了n下标位置(越界)
解决方法:1.n-1? ->0
? ? ? ? ? ? ? ? ? 2. cur--? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? 3.dest-=2
若遇到边界情况,最后的下标
class Solution
{
public:
void duplicateZeros(vector<int>& arr)
{
//1.找到最后一个复写的数
int cur = 0, dest = -1, n = arr.size();
while(cur<n)
{
if(arr[cur])
{
dest++;
}
else
{
dest += 2;
}
if(dest >= n-1)
{
break;
}
cur++;
}
//走到这里dest要么是n-1下标位置,要么是n下标位置
//2.处理n下标位置的边界情况
if(dest == n)
{
arr[n-1] = 0;
cur--;
dest -= 2;
}
//走到这里cur是最后一个要复写的数
//3.从后往前复写0
while(cur>=0)
{
if(arr[cur])
{
arr[dest--] = arr[cur--];
}
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};