优先算法 —— 双指针系列 - 移动零

1. 移动零

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

https://leetcode.cn/problems/move-zeroes/description/

2. 算法原理

其实像移动零这种类型的题目都有一个名字叫做数组划分（数组分块），就是说先给一个数组，然后再制定一个标准/规则，在这个标准/规则下将这个数组划分为诺干个区间 而在我们移动零这道题目里面就是先给一个数组，然后根据规则划分为两个区间

而解决这种类型的题目我们一般就是使用双指针算法来解决，在数组中，我们是利用数组的下标来充当指针的

我们先定义两个指针：dest：目的地 cur：当前的 两个指针的作用dest在已经处理的区间内，非0元素的最后一个位置cur从左往右遍历数组

那么我们就会划分为三个区间： [0,dest]表示已经处理过的区间，表示非0元素[dest+1,cur-1]全部都是0[cur,n-1]待处理的元素

当cur指针到达n位置的时候时候，那就说明cur已经从左往右把数组遍历一遍，那么我们这个区间就已经划分好了 当cur指针到达n位置的时候时候，那么待处理的区间就已经不存在了，然后整个区间就只剩下非0元素区间和0元素区间两个部分，就变成了我们上面所说的数组划分（数组分块）模式

让cur为0，dest为-1

3. 代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //这里cur++就不需要写遇到0元素cur++的情况了
        for(int dest=-1,cur=0;cur<nums.size();cur++)
            if(nums[cur])//如果cur遇到的是非0元素则交换
            //这里dest前置++可以直接将dest后面的一个元素直接交换
                swap(nums[++dest],nums[cur]);//因为for循环已经++，所以这里的cur不用++
    }
};

始源