【优选算法】专题1 -- 双指针 -- 移动零

前言:

📚为了提高算法思维，我会时常更新这个优选算法的系列，这个专题是关于双指针的练习

🎯个人主页：Dream_Chaser～-CSDN博客

一.移动零（easy）

描述：

「数组分两块」是⾮常常⻅的⼀种题型，主要就是根据⼀种划分⽅式，将数组的内容分成左右两部分。这种类型的题，⼀般就是使⽤「双指针」来解决。

题目链接： . 移动零 - 力扣（LeetCode）

题目描述：

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

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

示例：

算法原理：

快速排序：快排里面最核心的那一步 -- 数据划分

推荐博客：回调函数(指针进阶2，详解，小白必看)

给你一个数组，然后给一个基准元素，设这个基准元素为tmp，根据这个元素把数组划分成两个部分：

但是快排也有缺陷：

当数据的值都是相差不大的时候(很多数据都是相等的)，时间复杂度是逼近 O(N^2) 的

解题思路：

我们就给按快排的原理对数组划分，数组分块：

📌 接着我们需要使用到双指针算法解决该题，本质是利用数组下标来充当指针

🚩两个指针的作用：

cur:从左往右扫描数组，遍历数组
dest:已处理的区间内，非零元素的最后一个位置 (基准元素tmp)

我们可以看到两个指针将这个数组分成了三个区间：

💥三个区间分别是：

如何实现：

cur 从前往后遍历的过程中:
        1.遇到 0 元素:cur++; (dest不动,cur从头到尾都要动)
        2.遇到非 0 元素:
                swap(dest + 1, cur);

                dest++，cur++;

图片解析:

原图：

循环结束标志：

动图：

编写代码：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int cur =0,dest = -1;cur<nums.size();++cur)
        {
            if(nums[cur])//处理非0元素
                swap(nums[++dest],nums[cur]);
        }
    }
};