【双指针算法】移动零

1.题目解析

2.算法分析

可以归结为数组划分/数组分块（采用双指针算法）-->利用数组下标充当指针

（1）首先定义两个指针 

• dest：已处理的区间内，非零元素的最后一个位置
• cur：从左往右扫描数组，遍历数组

（2）将数组划分为三个部分:

• [0,dest]：已处理的元素，全部为非0
• [dest+1,cur-1] ：全部为0
• [cur,n-1]：待处理元素

（3）cur从前往后移动的过程

• 遇到0，直接cur++
• 遇到非0元素，swap（des+1，cur），cur++，des++

双指针算法是快排最核心的一步，设置基准元素tmp，左边让他都小于tmp，右边让他都小于tmp

3.代码编写

class Solution {public void moveZeroes(int[] nums) {int dest=-1;int cur=0;while(cur<nums.length){if(nums[cur]==0){cur++;}else{int tmp=nums[dest+1];nums[dest+1]=nums[cur];nums[cur]=tmp;cur++;dest++;}}} 
}

4.复杂度分析

时间复杂度：O(N)

空间复杂度：O(1)