当前位置：首页 > article >正文

双指针---《移动零》

article 2025/3/31 9:00:33

文章前言

题目描述

算法原理讲解

忽略限制条件的解法

原理讲解

思路总结

代码展示

双指针解法

原理讲解

思路总结

代码展示

大总结

💫只有认知的突破💫才来带来真正的成长💫编程技术的学习💫没有捷径💫一起加油💫

🍁感谢各位的观看🍁欢迎大家留言🍁咱们一起加油🍁努力成为更好的自己🍁

文章前言

为了提高自己的编程技术和能力，本博主开始要更新相关算法题的内容了。我会分类型的进行算法题的讲解，由于博主是第一次真正意义上接触系统的刷题训练，作为一个小白，有不足或错误的地方，很愿意听取在座各位大佬的批评和指教。废话不多说，让我们开启刷算法题的旅行吧！

题目描述

题目链接：移动零

如图所示的要求：

给你一个数组，要求把这个数组的0元素，全部移动到数组的后面，非0元素全部移动到数组的前面，而且这些非0元素的相对顺序保持不变。注意：不能新开辟一个数组，然后再把这新数组里面的元素拷贝到以前的数组中，这是不允许的，只能在原数组上进行操作。

算法原理讲解

忽略限制条件的解法

本博主在一开始写这个题目的时候，就没有注意到限制条件——不允许开辟数组。虽然，这个解法能在Leetcode上能通过，但是不符合题目要求。我想把这个写法也保留下来，它也算是一种思想，万一在别的题目就合适呢！

原理讲解

创建一个和原数组空间大小一样的新数组，在这个新数组上，创建两个“指针”，这里的指针不是真正的指针，就是通过下标访问的变量。第一个指针begin_num指向数组的首元素，第二个指针end_num指向数组的最后一个元素，如图所示(以示例1为例)：

然后再去遍历原数组，遇到0元素，就存放在end_num，然后end_num再向前 - - ，为存储下一个0元素做准备，当遇到非0元素时，就存放在begin_num，然后begin_num向后走 + +，为下一个非0元素做准备，直到原数组遍历完毕。如图所示：

思路总结

1.新建立和原数组一样大的数组

2.创建两个“指针”，分别指向新数组的头和尾处的空间

3.依次遍历原数组

3.1：遇到0元素，就插入end_num，然后end_num- -

3.2：遇到非0元素，就插入begin_num，然后begin_num++

4.原数组访问完毕就结束

5.在把新数组排好序的元素赋值拷贝给原数组

代码展示

class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        vector<int>num(nums.size(),1);  //开辟一样大小的新数组
     
        //创建两个指针
        auto end_num=num.end()-1;    //指向新数组的首元素
        auto begin_num=num.begin();    //指向新数组的尾元素
        for(auto&e:nums)
        {
            if(e==0)        //0元素插入end_num
            {
                *end_num=e;
                end_num--;
            }
            else            //非0元素插入begin_num
            {
                *begin_num=e;
                begin_num++;
            }
        }
        nums=num;        //把排好序的新数组赋值拷贝给原数组
    }
};

双指针解法

原理讲解

我们解题时，所谓的双指针并不是真正的指针，不是int*,char*……。而是指向数组的下标变量，比如，0，1，2……。所以大家不要感到害怕。

因为题目要求只能在原数组进行操作，所以我们就要摒弃开辟新数组的思想了。根据题目要求：非0元素全部在数组的左边，0元素全部在数组的右边。使用新的思想：数组划分(数组分块)的思想,这个数组被划分为两个区域，一块是非0区域，另一块是0区域，如图所示：

这个时候，创建两个指针，一个是cur，另一个是dst。cur指针的作用：它把数组分为已处理和待处理的两个部分。dst指针的作用：它把已处理过的数组分为，左边全是非0元素(保持相对顺序)和右边全是0元素的两个部分。所以，这俩指针把数组分为3个部分。如图所示：

所以数组被分为三个区间：[0,dst] , [dst+1,cur-1] , [cur,n-1]。[0,dst]全是非0元素，[dst+1,cur-1]全是0元素，[cur,n-1]待处理。其中，dst指向非0元素区间的最后一个非0元素。在遍历数组的过程中，始终保持这三个区间的性质不变，就会达到题目要求。让cur=0指向首元素位置，因为要起始遍历数组。对于dst，要使它指向首元素的前一个位置，dst=-1。因为dst指向的是非0元素，在起始位置，是无法确定起始元素是否为非0元素，所以就把dst放在前面。如图所示：

当cur指向的元素是0时，dst不动。当cur指向的元素非0时，dst++,然后cur和dst指向的元素进行交换，然后cur继续往后走，直到遍历完数组结束。

思路总结

1.cur=0指向首元素，dst=-1指向数组前面

2.cur指向的元素为0 , dst不动

3.cur指向的元素非0，dst++

3.1:然后swap(dst元素，cur元素)

3.2：cur++往后走

4.cur遍历完数组结束

代码展示

class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        for(int dst=-1,cur=0;cur<nums.size();cur++)
            if(nums[cur])
                swap(nums[++dst],nums[cur]);
    }
};