1 问题

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1

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

示例 2

输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 104
-$2^{31}$ <= nums[i] <= $2^{31}$ - 1

进阶：你能尽量减少完成的操作次数吗？

2 解题思路

2.1 快排思想

回忆下快排，基本思想是

确定一基准pivot：
- 若右指针right所指向的值比pivot大，则right--；
- 否则交换这两值，然后比较左指针left指向的值；
  - 若pivot大于left所指的值，left++；
  - 否则，交换pivot和left所指的值。

总之，快排的思想一句话就是，将数组排列成一个以基准值为准，左侧是比基准值小的值，右侧是比基准值大的值。

本题中，基准值为0，只要right所指的值不为0，就与left所指的值交换，left++.循环right，则不为0的值就都在左边了。
双指针算法示意图

2.2 两次遍历

我们创建两个指针 i 和 j，第一次遍历的时候指针 j 用来记录当前有多少非0 元素。即遍历的时候每遇到一个 非0 元素就将其往数组左边挪，第一次遍历完后，j 指针的下标就指向了最后一个 非0 元素下标。
第二次遍历的时候，起始位置就从 j 开始到结束，将剩下的这段区域内的元素全部置为 0。
动画演示：
两次遍历

转自作者：王尼玛

3 代码

class Solution {
  //两次遍历
  public void moveZeroes(int[] nums) {
    if (nums == null) {
      return;
    }
    //第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
    int j = 0;
    for (int i = 0; i < nums.length; ++i) {
      if (nums[i] != 0) {
        nums[j++] = nums[i];
      }
    }
    //非0元素统计完了，剩下的都是0了
    //所以第二次遍历把末尾的元素都赋为0即可
    for (int i = j; i < nums.length; ++i) {
      nums[i] = 0;
    }
  }

  //双指针
  public void moveZeroes2(int[] nums) {
    //left指向第一个为0的元素索引
    int left = 0;
    int right = 0;
    for (; right < nums.length; right++) {
      // 当前元素!=0，就把其交换到左边，等于0的交换到右边
      if (nums[right] != 0) {
        int tmp = nums[right];
        nums[right] = nums[left];
        nums[left] = tmp;
        left++;
      }
    }
  }

  //一次遍历
  public void moveZeroes3(int[] nums) {
    int cnt = 0;
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] == 0) {
        cnt++;
      } else if (nums[i] != 0 && cnt > 0) {
        nums[i - cnt] = nums[i];
        nums[i] = 0;
      }
    }
  }
}