LeetCode —— 复写零(双指针)

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析

将数组中出现的每个零复写一遍，然后将其他元素向右平移，数组长度不能改变。

法一：使用额外空间的做法

class Solution 
{
public:void duplicateZeros(vector<int>& arr) {// 定义一个额外的vectorvector<int> v;// 遍历数组for(auto&e:arr){// 如果该元素不为0，则向新数组中插入一个该元素if(e) v.push_back(e);// 如果该元素为0，则向新数组中插入两个该元素else{v.push_back(0);v.push_back(0);}}// 改变新数组的大小为老数组大小v.resize(arr.size());// 将老数组赋值给新数组arr=v;}
};

法二：原地修改的做法

 

 

class Solution 
{
public:void duplicateZeros(vector<int>& arr) {int n=arr.size();int cur=0,dest=-1;// 找最后一个复写的元素while(cur<n){if(arr[cur]==0) dest+=2;else dest++;if(dest>=n-1) break;cur++;}// 处理边界情况if(dest==n){arr[n-1]=0;cur--;dest-=2;}// 覆盖while(cur>=0){if(arr[cur]==0){arr[dest--]=arr[cur];arr[dest--]=arr[cur--];}else{arr[dest--]=arr[cur--];}}}
};