[优选算法]——双指针——Leetcode——1089. 复写零

目录

1.题目

 2.解法（原地复写-双指针）：

1.算法思路：

2.算法流程：

     3.手撕流程图 

先根据“异地”操作，然后优化成双指针下的“就地”操作

 找到最后⼀个复写的数：

 4.代码实现

1.C语言

2.C++ 

---

1.题目

1089. 复写零

给你一个长度固定的整数数组 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

 2.解法（原地复写-双指针）：

1.算法思路：

如果「从前向后」进⾏原地复写操作的话，由于? 0 ?的出现会复写两次，导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」，因此我们的⼤体流程分两步：
i. 先找到最后⼀个复写的数；（最重要的一步）
ii. 然后从后向前进⾏复写操作。

2.算法流程：

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-- ，复写下⼀个位置。

     3.手撕流程图 

先根据“异地”操作，然后优化成双指针下的“就地”操作

 找到最后⼀个复写的数：

 4.代码实现

1.C语言

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--;
        }
    }
}

2.C++ 

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--;
        }
       }
    }
};