LeetCode —— 复写零(双指针)

题目链接

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

题目解析

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

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

class Solution 
{
public:
    void duplicateZeros(vector<int>& arr) 
    {
        // 定义一个额外的vector
        vector<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
        {
            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--];
            }
        }
    }
};