优选算法|【双指针】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++;
        }
    }
}