优选算法|【双指针】283.移动零

简介: 优选算法|【双指针】283.移动零

题目

283. 移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]


输出: [1,3,12,0,0]



示例 2:

输入: nums = [0]


输出: [0]

提示:

  • 1 <= nums.length <=
  • - <= nums[i] <= - 1

题目解析

题目中说,给定一个一维数组,要求

1.将一维数组中的0的都移到这个数组的后边,

2.保证数组的中原来非0元素的相对顺序

3.不能复制数组进行,也就是说,空间复杂度为0.

讲解算法原理

       这道题都可以归到数组划分(数组分块)这一类题里面。

       数组划分这类题的特点是,给定一个数组,通过一系列变化,将数组划分成若干个区域,例如这个题就是通过将数组中零元素的移动,将数组划分成非零元素和零元素两个区域。

       解决这类题,首先想到的就是双指针算法,对于数组的题目,这里的指针不是地址的意思,而是数组下标的意思。

       首先我们先定义两个指针,cur(current在英语里面是当前的现在的意思)dest(destnation有目的地id意思)

他们的作用:

cur:从左往右扫描遍历数组,因此cur前面的都是处理过的元素,dest后边都是未处理的元素,cur也是未处理段的第一个元素

dest:非零元素和零元素的分割线,因此在已扫描的区间内,dest前面的都是非零元素,dest后边是零元素,dest也是最后一个非零元素的位置

这两个指针也将数组分成了三个部分

0—dest:已处理的非零元素

dest—1-cur-1:已处理的零元素

cur—numsSize-1:未处理

我们要使每次移动cur和dest都可以将整个数组分成这三个区间。

       那么什么时候结束呢,当然是当cur扫描完整个数组,数组中dest就把整个数组分成(非零段和零段)两个部分。

上面说过cur指向待处理段的第一个元素,dest指向处理段的最后一个非零元素,刚开始时,第一个元素就未处理,所以cur应该指向第一个元素,dest应该指向-1.

接下来要开始移动了,因为dest和cur之间是零,所以cur在遇到零的时候直接+1就行。

       当cur遇到非零数字的时候,因为非零数字应该在0—dest这个区间内,而现在dest指向-1所以应该将dest+1然后将dest所指向的值和cur所指向的值进行交换。然后cur在进行+1。

先在cur所指向的值又是1所以直接+1就行。

这个是cur遇到非零数字的时候那就是dest+1,然后交换,交换之后就行。结果如下

接下来,还是cur遇到数字的情况

直到cur指向结尾的下一个就结束了

代码

void moveZeroes(int* nums, int numsSize) 
{
    int cur=0;
    int dest=-1;
    while(cur<numsSize)
    {
        if(nums[cur]==0)cur++;
        else {
            dest++;
            int temp=nums[dest];
            nums[dest]=nums[cur];
            nums[cur]=temp;
            cur++;
        }
    }
}
相关文章
|
16天前
|
机器学习/深度学习 搜索推荐 算法
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
|
1天前
|
人工智能 算法 网络性能优化
【调度算法】服务组合优选问题的指标选择与评估
【调度算法】服务组合优选问题的指标选择与评估
12 0
|
7天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
7天前
|
算法 容器
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和
|
16天前
|
算法
【算法优选】 动态规划之两个数组dp——壹
【算法优选】 动态规划之两个数组dp——壹
|
16天前
|
人工智能 算法
【算法优选】 动态规划之子数组、子串系列——贰
【算法优选】 动态规划之子数组、子串系列——贰
|
16天前
|
机器学习/深度学习 算法 测试技术
【算法优选】 动态规划之子数组、子串系列——壹
【算法优选】 动态规划之子数组、子串系列——壹
|
16天前
|
算法
【算法优选】 动态规划之简单多状态dp问题——贰
【算法优选】 动态规划之简单多状态dp问题——贰
|
27天前
|
存储 人工智能 算法
c++算法学习笔记 (9) 双指针
c++算法学习笔记 (9) 双指针
|
28天前
|
算法
【优选算法】——滑动窗口——1004. 最大连续1的个数 III
【优选算法】——滑动窗口——1004. 最大连续1的个数 III