每日一练：【优先算法】双指针之移动零（easy）

双指针概念介绍

常见的双指针有两种形式，一种是对撞指针，一种是左右指针。

对撞指针：一般用于顺序结构中，也称左右指针。
• 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
• 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循
环），也就是：
◦ left == right （两个指针指向同一个位置）
◦ left > right （两个指针错开）

快慢指针：又称为龟兔赛跑算法

其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。
快慢指针的实现方式有很多种，最常用的一种就是：
• 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。

注：上述双指针是一种抽象的概念，对于像数组的结构，我们是通过记录对应的位置来达成像指针的效果，并不一定是创建指针

1. 题目链接：283. 移动零

题目分析：

本题我们需要将非零元素移动到数组前面，并且保持相对位置不变，非零元素的之后都是0,0不要求相对顺序不变，，根据题目条件限制，不能复制数组，意味着算法的空间复杂度为0。

要将非零数放到前面，0放到后面，原地的情况下，我们只能采用交换的方法。因此这里我们使用双指针的方法。

由于需要保持非0数的相对顺序，这就意味着算法需要具有一定的稳定性，如果双指针是对向移动，那么数字的相对顺序就会改变。因此指针一定是同向移动的。

算法原理

观察数组，发现数组整体是分成两部分的，非零元素放在一块，零元素放在一块，再基于题目分析中的条件，这题我们采用数组分块的思想（这也是快排的一种实现思想）。

我们创建dest与src指针（效果上的指针，实际上通过[]+下标实现）我们将dest初始化为-1，src初始化为0，通过dest与src的交错，我们就将数组划分成三个部分。

dest左边是已处理的数据，也就是我们非零数将要存放的位置，dest与src之间的区间将要将要存放0，src右边的区间是还没有处理的数据。

每一次遇到0，src++，dest不动，每一次dest之间区间长度的变化都是因为遇到0，这样src与dest之间相差的就都是0了，遇到非0数，因为dest指向的位置及其左边的区间是已经处理完的数即非0数，我们不能直接交换dest与src指向的值，我们先将++dest,dest指向0，src指向非0值，我们再将dest与src指向值交换，再将src++，这样非0值始终在dest指向的左区间，0始终在dest与src之间，src指向及右区间是未处理数据。当src出数组，就说明所以数据处理完，循环结束。

算法代码

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

};

原文地址：https://blog.csdn.net/2401_82610555/article/details/143871272

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！