优选算法|【双指针】|1089.复写零

简介: 优选算法|【双指针】|1089.复写零



题目描述

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

题目解析

       题目意思就是遇到0了再写一遍0,其他元素向右平移就行。只能在原来数组上修改,也就是空间复杂度为0.

算法原理讲解

       一般像这种在数组中移动一些数的题目,也是用双指针算法来解决这个问题。

      双指针算法是根据异地解法的操作,优化成双指针的就地操作。

异地操作

异地操作就是,重新开辟一个数组。

       定义两个指针,cur用来扫描原数组,dest用来更新新数组。

       当cur对应的值不等于0时,dest更新一个数,将cur值直接填入dest的位置,dest++,cur++就行。

       当cur对应的值等于0时,dest指针更新两个数,都填入0,cur++就行。

       当dest=arrSize就结束了。

就地操作

       就是不用重新开辟数组,也就是题目要求的那样,我们可以把cur和dest这两个指针,都放在原数组上。

      用双指针解决复写问题的步骤

1.找到最后一个复写的数

2.从后向前完成复写

       让cur指向最后一个复写的数,对于[1,0,2,3,0,4,5,0]这个数组,最后一个复写的数是4,所以让cur指向4 ,best指向最后一个位置就行。

cur指向的这个数是非零的,所以复写一次就行,复写完后,cur--,dest--。

这次cur指向0,那就复写两次,后cur--。

从图中可以看出,当cur和dest都指向-1的时候就复写完成了。

接下来有一个问题就是?——怎么找到最后一个复写的数

       还是利用双指针算法,定义两个指针cur和dest,cur用来扫描数组,dest用来标识最后一个复写的数。

cur指向的值决定dest向后移动两步还是移动一步

1.先判断cur里面的值

2.决定dest走两步还是走一步

3.在判断dest到没到结尾

4.没到结尾再cur++

       咱们一步一步来,arr[cur]现在指向了1,所以dest走一步到达下标为0的位置,dest没有走到结尾,所以cur++。

arr[cur]现在指向了0,所以dest走两步到达下标为2的位置,dest没有走到结尾所以cur++。

arr[cur]现在指向了2,所以dest走一步到达下标为3的位置,dest没有走到结尾所以cur++。

arr[cur]现在指向了3,所以dest走一步到达下标为4的位置,dest没有走到结尾所以cur++。

arr[cur]现在指向了0,所以dest走两步到达下标为6的位置,dest没有走到结尾所以cur++。

arr[cur]现在指向了4,所以dest走一步到达下标为7的位置,dest走到结尾返回cur。

       对于这个数组这种方法是刚好的,那么如果是【1,0,2,3,0,4】

arr[cur]现在指向了1,所以dest走一步到达下标为0的位置,dest没有走到结尾所以cur++。

arr[cur]现在指向了0,所以dest走两步到达下标为2的位置,dest没有走到结尾所以cur++。

arr[cur]现在指向了2,所以dest走一步到达下标为3的位置,dest没有走到结尾所以cur++。

arr[cur]现在指向了3,所以dest走一步到达下标为4的位置,dest没有走到结尾所以cur++。

        arr[cur]现在指向了0,所以dest走两步到达下标为6的位置,但是这个数组没有下标6最大直到5,所以会产生越界。

       接下来,我们怎么解决这个问题,我们要明白越界是怎么产生的,是因为复写0,复写两次就产生了越界。这个情况我们单独处理一下。

那么怎么处理呢?我们在复写的时候将最后一个位置,和越界的那个位置都复写成0。但是越界那个位置不能修改成0,我们只需要把最后一个位置修改成0(直接在这里复写),也就是arr[arrSzie-1]=0,就可以。

修改之后我们将dest向前移动两步,cur向前移动一步

cur现在就是最后一个复写的值,接下来复写就从dest现在的位置开始复写。

代码

void duplicateZeros(int* arr, int arrSize) {
    //找到最后一个复写的位置
    int cur=0;
    int dest=-1;
    while(cur<arrSize)
    {
        if(arr[cur]==0)dest+=2;
        if(arr[cur]!=0)dest+=1;
        //如果dest到达最后一个位置就跳出循环
        //如果刚好的话是等于arrSzie-1,有越界的时候是等于arrSize
        if(dest==arrSize-1||dest==arrSize)break;
        cur++;
    }
    //处理边界
    if(dest==arrSize)
    {
        arr[arrSize-1]=0;
        cur-=1;
        dest-=2;
    }
    while(cur>=0&&dest>=0)
    {
        if(arr[cur]==0)
        {
            arr[dest--]=arr[cur];
            arr[dest--]=arr[cur--];
        }
        else
        {
            arr[dest--]=arr[cur--];
        }
    }
    
}
相关文章
|
10天前
|
机器学习/深度学习 搜索推荐 算法
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
|
22小时前
|
算法 容器
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
|
10天前
|
算法
【算法优选】 动态规划之两个数组dp——壹
【算法优选】 动态规划之两个数组dp——壹
|
10天前
|
人工智能 算法
【算法优选】 动态规划之子数组、子串系列——贰
【算法优选】 动态规划之子数组、子串系列——贰
|
10天前
|
机器学习/深度学习 算法 测试技术
【算法优选】 动态规划之子数组、子串系列——壹
【算法优选】 动态规划之子数组、子串系列——壹
|
10天前
|
算法
【算法优选】 动态规划之简单多状态dp问题——贰
【算法优选】 动态规划之简单多状态dp问题——贰
|
21天前
|
存储 人工智能 算法
c++算法学习笔记 (9) 双指针
c++算法学习笔记 (9) 双指针
|
22天前
|
算法
【优选算法】——滑动窗口——1004. 最大连续1的个数 III
【优选算法】——滑动窗口——1004. 最大连续1的个数 III
|
22天前
|
算法 C++
【优选算法】——滑动窗口——3. 无重复字符的最长子串
【优选算法】——滑动窗口——3. 无重复字符的最长子串
|
1天前
|
算法 安全
基于龙格库塔算法的SIR病毒扩散预测matlab仿真
该程序使用龙格库塔算法实现SIR模型预测病毒扩散,输出易感、感染和康复人群曲线。在MATLAB2022a中运行显示预测结果。核心代码设置时间区间、参数,并定义微分方程组,通过Runge-Kutta方法求解。SIR模型描述三类人群动态变化,常微分方程组刻画相互转化。模型用于预测疫情趋势,支持公共卫生决策,但也存在局限性,如忽略空间结构和人口异质性。