每日算法【双指针算法】(Day 1-移动零)

1.算法题目（移动零）

2.讲解算法原理

数组划分，数组分块（快排里面最核心的一步）只需把0改为tmp

双指针算法：利用数组下标来充当指针

两个指针的作用：
cur:从做往右扫描数组，遍历数组
dest:已处理的区间内，非零元素的最后一个位置

三个区间：
[0,dest] ,[dest+1,cur-1] , [cur,n-1]
按序依次是非0，0，待处理

• 当cur=n时 变成

先让dest指向下标为-1的位置，cur指向下标为0的元素，此时元素为0，cur++,cur指向的元素为1，这时dest++,然后交换dest和cur指向的元素，也就是交换0和1的位置。
总结：cur从前往后遍历的过程中

1. 遇到0元素：cur++
2. 遇到非0元素：

swap(dest+1,cur);
dest++,cur++;

3.编写代码

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