双指针——移动零

一，题目要求：

• 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
  请注意 ，必须在不复制数组的情况下原地对数组进行操作。

  • 示例 1:
    输入: nums = [0,1,0,3,12]
    输出: [1,3,12,0,0]

  • 示例 2:
    输入: nums = [0]
    输出: [0]

  • 提示:
    1 <= nums.length <= 104
    -231 <= nums[i] <= 231 - 1

二 ，算法原理

• 定义两个指针
  • cur从左向右扫描数组，遍历数组
  • dest指向处理区间内，非0元素的最后一个元素
• 将数组分成三个部分：
  • 【0，dest】：非0元素
  • 【dest+1，cur-1】：0元素
  • 【cur，n-1】：待处理

• cur从左向右遍历：保持这三部分的状态不变，当遍历结束时，即完成非0元素与0元素的划分。

  • cur 遇到0元素：
    cur ++
  • cur 遇到非0元素：
    非0元素部分长度+1，并把cur当前所指的这个非0元素添加到这个新增的这个位置，即swap（dest+1，cur）。
    

三 ，代码实现

public void moveZeroes(int[] nums) {

	// 遍历之前，非0元素部分长度为0，所以dest = -1

	for(int cur = 0,dest = -1;cur < nums.length;cur ++) {
	
		if(nums[nums] != 0) {
			dest ++;      // 非0元素部分长度+1

			// 交换新增位置处的0 和 cur当前指向的值
			int tmp = nums[cur];
			nums[cur] = nums[dest];
			nums[dest] = tmp;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16