给你一个长度固定的整数数组 arr
,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。
注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。
示例 1:
输入:arr = [1,0,2,3,0,4,5,0]
输出:[1,0,0,2,3,0,0,4]
解释:调用函数后,输入的数组将被修改为:[1,0,0,2,3,0,0,4]
示例 2:
输入:arr = [1,2,3]
输出:[1,2,3]
解释:调用函数后,输入的数组将被修改为:[1,2,3]
提示:
1 <= arr.length <= 104
0 <= arr[i] <= 9
如果「从前向后」进⾏原地复写操作的话,由于? 0 ?的出现会复写两次,导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。但是「从后向前」复写的时候,我们需要找到「最后⼀个复写的数」,因此我们的⼤体流程分两步: i. 先找到最后⼀个复写的数;(最重要的一步) ii. 然后从后向前进⾏复写操作。
a. 初始化两个指针 cur = 0 , dest = 0 ;
b. 找到最后⼀个复写的数: i. 当cur < n 的时候,⼀直执⾏下⾯循环: • 判断 cur 位置的元素: ◦ 如果是 0 的话, dest 往后移动两位; ◦ 否则, dest 往后移动⼀位。 • 判断?dest ?时候已经到结束位置,如果结束就终⽌循环; • 如果没有结束, cur++ ,继续判断。 c. 判断dest 是否越界到 n 的位置: i. 如果越界,执⾏下⾯三步: 1. n - 1 位置的值修改成0 ; 2. cur 向移动⼀步; 3. dest 向前移动两步。
d. 从cur 位置开始往前遍历原数组,依次还原出复写后的结果数组: i. 判断cur 位置的值: 1. 如果是 0 : dest 以及 dest - 1 位置修改成 0 , dest -= 2 ; 2. 如果⾮零: dest 位置修改成0 , dest -= 1 ; ii. cur-- ,复写下⼀个位置。
先根据“异地”操作,然后优化成双指针下的“就地”操作
void duplicateZeros(int* arr, int arrSize)
{
//先找到最后一个复写数
int cur=0,dest=-1;
while(cur<arrSize)
{
if(arr[cur])
{
dest++;
}
else
{
dest+=2;
}
if(dest>=arrSize-1)
{
break;
}
cur++;
}
//处理边界情况
if(dest==arrSize)
{
arr[ arrSize-1]=0;
cur--;
dest-=2;
}
//3.从后往前完成复写操作
while(cur>=0)
{
if(arr[cur])//不为零是复写一次
{
arr[dest--]=arr[cur--];
}
else//为零时
{
arr[dest--]=0;
arr[dest--]=0;
cur--;
}
}
}
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
int cur=0,dest=-1,n=arr.size();
while(cur<n)
{
if(arr[cur]) dest++;
else dest+=2;
if(dest>=n-1) break;
cur++;
}
if(dest==n)
{
arr[n-1]=0;
cur--;
dest-=2;
}
while(cur>=0)
{
if(arr[cur]) arr[dest--]=arr[cur--];
else
{
arr[dest--]=0;
arr[dest--]=0;
cur--;
}
}
}
};