题目：https://leetcode-cn.com/problems/move-zeroes/

image.png

题目有两个要求：

  • 将所有 0 移到数组的末尾。
  • 所有非零的数字保持顺序。

方法一：双指针

思路其实就是找非零数字需要插入的索引位置。

假设数组为 [0, 0, 2, 3] ，在遍历的时候，我们找到0的索引位置为0，此时就需要记住这个索引位置就是下一个非零数字需要插入的地方。下一个非零数字“2”的索引为2，经值交换后，数组变为 [2, 0, 0, 3] 。

此时数组继续遍历，得到 0 的索引位置为 1，此时非零数字要插入的索引位置就为1了。而下一个非零数字“3”的索引为 3，经值交换后数组变为 [2, 3, 0, 0] 。

而下面的题解，就是上面思路的实现：

  1. /**
  2.  Do not return anything, modify nums in-place instead.
  3.  */
  4. function moveZeroes(nums: number[]): void {
  5.     // 记录非零数字需要插入的索引位置
  6.     let insertIndex = 0;
  8.     for (let i = 0; i < nums.length; i++) {
  9.         // 找出非零元素，并将非零元素插入到 insertIndex 位置
  10.           // 仅需找出 nums[i] !== 0 的情况即可，nums[i] === 0 的情况下交换值没有任何意义，因为值都是0
  11.         if (nums[i] !== 0) {
  12.             if (i !== insertIndex) {
  13.                 nums[insertIndex] = nums[i]
  14.                 nums[i] = 0
  15.             }
  17.               // 下面一步之所以注释，是因为这一步是多余的，因为如果索引一致的话，表明它们的值都是一致的，
  18.               // 因此完全没有必要在进行值交换的操作
  19.               // if (i === insertIndex) {
  20.               //   const tmp = nums[insertIndex]
  21.             //      nums[insertIndex] = nums[i]
  22.               //   nums[i] = tmp
  23.             // }
  25.             insertIndex++
  26.         }
  27.     }
  28. };

复杂度分析：

  • 时间复杂度：283. 移动零 - 图2
  • 空间复杂度：283. 移动零 - 图3

方法二：使用 JavaScript 原生 Api

直接使用 JavaScript 是最为简洁易懂的，直接使用 splice() 来删除数组中的 0 元素，然后再向数组末尾添加 0。具体解法如下：

  1. /**
  2.  Do not return anything, modify nums in-place instead.
  3.  */
  4. function moveZeroes(nums: number[]): void {
  5.     for (let i = 0, count = 0; count < nums.length; count++) {
  6.         if (nums[i] === 0){
  7.             nums.splice(i, 1)
  8.             nums.push(0)
  9.         } else {
  10.             i++
  11.         }
  12.     }
  13. };

复杂度分析：

  • 时间复杂度为 283. 移动零 - 图4
  • 空间复杂度为 283. 移动零 - 图5

正常来说，是直接使用自增的 i 来读取数组元素，但是由于使用 spilice api 后，已经更改了数组元素的索引了，如果此时仍然继续使用自增的 i，此时其实是会跳过一些元素的。以下面的代码为例可以看出问题所在。

  1. const arr = [0, 1, 2, 0, 3]
  2. for (let i = 0; i < arr.length; i++) {
  3.      if (arr[i] === 0) {
  4.     arr.splice(i, 1)
  5.     arr.push(0)
  6.   }
  7. }
  10. // 第一次循环结果：
  11. // arr [ 0, 1, 2, 0, 3 ]
  12. // arr[i] 0
  14. // 第二次循环结果：
  16. // arr [ 1, 2, 0, 3, 0 ]
  17. // arr[i] 2
  19. // 第三次循环结果：
  21. // arr [ 1, 2, 0, 3, 0 ]
  22. // arr[i] 0
  24. // 第四次循环结果：
  26. // arr [ 1, 2, 3, 0, 0 ]
  27. // arr[i] 0
  29. // 第五次循环结果：
  31. // arr [ 1, 2, 3, 0, 0 ]
  32. // arr[i] 0

我们从结果可以看出， arr[i] 所打印的结果是有遗漏的。因此在解法中，使用了 count 变量来限制循环次数与数组的元素个数一致。

变量 i 则主要用于读取数组的元素，在对数组进行了操作的时 i 的数值是不会做增加的操作，因为此时索引 i 的元素已经变为原来 i+1 的元素，所以如果 i 在加 1 的话，其实就会跳过了一个元素。

方法三：找出所有非零元素与零元素

思路：找出所有的非零元素和零元素。

  1. /**
  2.  Do not return anything, modify nums in-place instead.
  3.  */
  4. function moveZeroes(nums: number[]): void {
  5.     // 获取 0 的个数
  6.     let zeroArr: number[] = []
  7.     nums.forEach(num => {
  8.         if (num === 0) {
  9.             zeroArr.push(0)
  10.         }
  11.     })
  13.     // 获取所有非 0 元素
  14.     const noneZeroNums: number[] = []
  15.     nums.forEach(num => {
  16.         if (num !== 0) {
  17.             noneZeroNums.push(num)
  18.         }
  19.     })
  21.     // 合并结果
  22.     const combineArr = noneZeroNums.concat(zeroArr)
  24.     // 替换合并结果
  25.     for(let i = 0; i < nums.length; i++) {
  26.         nums[i] = combineArr[i]
  27.     }
  28. };

复杂度分析：

  • 时间复杂度：283. 移动零 - 图6
  • 空间复杂度：283. 移动零 - 图7

方法四：sort 排序

  1. /**
  2.  Do not return anything, modify nums in-place instead.
  3.  */
  4. function moveZeroes(nums: number[]): void {
  5.     nums.sort((a, b) => b === 0 ? -1 : 0)
  6. };

sort 的结果受回调函数返回值的影响：

  • 当回调函数返回的值小于0时，a 的索引比 b 的索引要小。
  • 当回调函数返回的值等于0时，a 的索引和 b 的索引不会有任何变化。
  • 当回调函数返回的值大于0是，a 的索引比 b 的索引要大。

需要注意的是，如果数组为 [1, 2] ，那么 a 的值为 2，而 b 的值为1。也就是说，a、b 的值的顺序与数组的顺序是相反的。我们只要判断 b 是否为0即可，当b为0，则将它置后。