算法题001——移动零

移动零

力扣——移动零点击链接即可跳转
在这里插入图片描述

这道题的数组被划分为两个区间，前一个区间为非零元素，而后一个指针是零元素
我们运用双指针，先定义两个指针，分别为 dest 和 cur , cur用来遍历整个数组，而 dest 表示我们已经处理完的数组的最后一个位置。
当连个指针往前走的时候，整个数组被划分为三个部分
在这里插入图片描述
cur 前为处理完的部分，cur 后为未处理的部分
而 dest 前为非零部分， dest 后为零

首先，定义 cur 从0 位置开始遍历，此时，并没有处理完的部分，所以定义 dest = -1;

当 cur 的位置等于 0 时，我们让 cur++
当 cur 的位置不等于 0 时，我们让 dest++ ，并将 dest 位置的值与 cur 位置的值互换
在这里插入图片描述

首先，定义 cur 从0 位置开始遍历，此时，并没有处理完的部分，所以定义 dest = -1;

cur 遍历的时候会遇到两种情况

当 cur 的位置等于 0
不做任何处理
当 cur 的位置不等于 0
遇到非零元素，我们想让非零元素到最左边，此时我们让 dest++ ，并将 dest 位置的值与 cur 位置的值互换即可实现

这就是这道题的原理，下面是代码实现

class Solution {public void moveZeroes(int[] nums) {for(int cur = 0,dest = -1;cur < nums.length;cur++){if(nums[cur] != 0){dest++;swap(nums,dest,cur);}}}private void swap(int[] array,int i,int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}
}