移动零
题目链接:https://leetcode.cn/problems/move-zeroes
题目的要求是不能改变原数组的非零元素的顺序,也不得再额外开个空间。
算法原理:将数组划分,数组分块。
将所有的非零元素移到左边,零元素移到右边。
方法:我们可以使用双指针算法,利用数组下标当作指针分别是 dest和cur俩个指针来划分区域
cur指针作用是从左向右遍历数组,dest的指针作用是已处理区间内非零元素的最后一个区域
意思就是我们可以分为三个部分,0到dest是非零元素在的区间,dest+1到cur-1是零元素在的区间,cur到num.size()-1是未处理的区间。
如何做到划分区间呢?
首先我们让dest放在-1的位置上,然后让cur从左向右遍历数组,在遍历过程中遇到俩种情况:第一种就是遇到零元素第二种就是遇到非零元素。我们cur遇到零元素的时候不处理,++cur,遇到零元素的时候,我们可以dest++一下,然后把nums[dest]和nums[cur]的位置交换一下,然后在++cur一下就行。