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

示例：

1
2
3
4
5
输入：nums = [0,1,0,3,12]
输出：[1,3,12,0,0]

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

提示：

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

心路历程

向后查找法

题目规定了不能复制数组，要原地进行操作，所以得用双指针。我开始想的是，一个指针找0，一个指针找不为0的，找到了就交换。然后开始尝试着写代码，结果发现执行栈溢出了，原来是我将while循环条件写成了不等于0，就导致在超过了原本数组的长度后，得到的值：undefined也能进入循环，然后形成了死循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var moveZeroes = function (nums) {
  if (nums.length === 0 || nums.length === 1) {
    return nums;
  }
  // 一个指针找0，一个找非0，然后交换，然后指针向后移动，直到找不到非0为止
  let i = 0;
  for (let j = 0; j < nums.length; j++) {
    if (nums[j] === 0 && j !== nums.length - 1) {
      i = j + 1;
      while (nums[i] !== undefined && (i < nums.length || nums[i] !== 0)) {
        if (nums[i] !== 0) {
          const temp = nums[i];
          nums[i] = nums[j];
          nums[j] = temp;
          break;
        }
        i++;
      }
    }
  }
  return nums;
};

上面的判断条件有些多余，改善一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var moveZeroes = function (nums) {
  if (nums.length === 0 || nums.length === 1) {
    return nums;
  }
  // 一个指针找0，一个找非0，然后交换
  let i = 0;
  for (let j = 0; j < nums.length; j++) {
    if (nums[j] === 0 && j !== nums.length - 1) {
      // 找非0的指针从找0的指针下一位开始
      i = j + 1;
      while (i < nums.length) {
        // 向后循环查找非0值
        if (nums[i] !== 0) {
          const temp = nums[i];
          nums[i] = nums[j];
          nums[j] = temp;
          break;
        }
        i++;
      }
    }
  }
  return nums;
};

依次定点法

有没有办法可以更快，步骤更少呢。上面我们还要向后遍历来找非0值，能不能去掉这一步。其实是可以的，甚至交换那一步也可以简化，我们用一个指针来分割，该指针的左边一定是非0值，然后依次从左到右交换过去，并更新指针位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var moveZeroes2 = function (nums) {
  if (nums.length === 0 || nums.length === 1) {
    return nums;
  }
  // 该指针表示从左到右中，当前未交换的点
  let i = 0;
  for (let j = 0; j < nums.length; j++) {
    const temp = nums[j];
    nums[j] = 0;
    if(temp !== 0){
      nums[i] = temp;
      i++;
    }
  }
  return nums;
};

还能有变体，也可以先交换，在看分割指针和当前循环指针是否指向同一处，如果不在同一处，说明必定存在0，那我们把0赋值给当前位置完成交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var moveZeroes3 = function (nums) {
  if (nums.length === 0 || nums.length === 1) {
    return nums;
  }
  // 该指针表示从左到右中，当前未交换的点
  let i = 0;
  for (let j = 0; j < nums.length; j++) {
    if (nums[j] !== 0) {
      // 先交换
      nums[i] = nums[j];
      if (j !== i) {
        nums[j] = 0;
      }
      i++;
    }
  }
  return nums;
};

最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var moveZeroes = function (nums) {
  if (nums.length === 0 || nums.length === 1) {
    return nums;
  }
  // 该指针表示从左到右中，当前未交换的点
  let i = 0;
  for (let j = 0; j < nums.length; j++) {
    const temp = nums[j];
    nums[j] = 0;
    if(temp !== 0){
      nums[i] = temp;
      i++;
    }
  }
  return nums;
};

参考链接