【双指针】001移动零_C++

题目链接：移动零

---

目录

题目解析

代码书写

知识补充

---

题目解析

题目让我们求必须在不复制数组的情况下,编写一个函数将所有?0?移动到数组的末尾，同时保持非零元素的相对顺序。

这题我们可以用双指针的方法来写：

我们这里将用两个数组下标来充当指针将该数组分为三个部分：

如图，这两个指针的作用：

cur：从左到右扫描数组，遍历数组；

dest：已处理的区间内，非零元素的最后一个位置

所以这三个区域的区间为：

已处理区（非0区间）：[0,dest]；

0区：[dest+1,cur-1];

待处理区：[cur-1,n]；

那么我们这里如何做到按照题目要求排序呢？

精髓就在于cur、dest的状态要和上面列出的区间一致；

当cur从前往后遍历的过程中：

? 1.当遇到0时，不做处理

? ? ? ? 这里就可以保证dest与cur间是0区；

? 2.遇到非零元素：

? ? ? ? 此时因为dest指向的是非零元素的最后一个，所以要把dest+1位置的0和cur位置的值交换

? ? ? ? 接着dest与cur继续向前走一步；

---

代码书写

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