第95题 将数组中的0移动到末尾

  • 如输入 [1,0,3,0,11,0] 输出 [1,3,11,0,0,0]
  • 只移动0其他顺序不变
  • 必须在原数组进行操作

如果不限制“必须在原数组进行操作”

  • 定义part1,part2两个数组
  • 遍历数组，非0 push到part1,0 push到part2
  • 返回合并part1.concat(part2)

思路分析

  • 嵌套循环：传统思路
    • 遇到0 push到数组末尾
    • 用splice截取当前元素
    • 时间复杂度是O(n^2) 算法基本不可用(splice移动数组元素复杂度是O(n)，for循环遍历数组复杂度是O(n)，整体是O(n^2))
    • 数组是连续存储空间，要慎用shift、unshift、splice等API
  • 双指针方式：解决嵌套循环的一个非常有效的方式
    • 定义j指向第一个0，i指向j后面的第一个非0
    • 交换i和j的值，继续向后移动
    • 只遍历一次，所以时间复杂度是O(n)

移动 0 到数组的末尾（嵌套循环）

    /**
     * 移动 0 到数组的末尾（嵌套循环）
     * @param arr:number[] number arr
     */
    function moveZero1(arr) {
      const length = arr.length
      if (length === 0) return
    
      let zeroLength = 0
    
      // 时间复杂度O(n^2)
      // ![](https://s.poetries.work/uploads/2023/01/2d09248cdc2c26ae.png)
      for (let i = 0; i < length - zeroLength; i++) {
        if (arr[i] === 0) {
          arr.push(0) // 放到结尾
          arr.splice(i, 1) // 在i的位置删除一个元素 splice本身就有 O(n) 复杂度
          // [1,0,0,0,1,0] 截取了0需要把i重新回到1的位置
          i-- // 数组截取了一个元素，i 要递减，否则连续 0 就会有错误
          zeroLength++ // 累加 0 的长度
        }
      }
    }

移动 0 到数组末尾（双指针）

    /**
     * 移动 0 到数组末尾（双指针）
     * @param arr:number[] number arr
     */
    function moveZero2(arr) {
      const length = arr.length
      if (length === 0) return
    
      // ![](https://s.poetries.work/uploads/2023/01/d2ae2e0f5f41368b.png)
      // [1,0,0,1,1,0] j指向0 i指向j后面的第一个非0（1），然后j和i交换位置，同时移动指针
      let i // i指向j后面的第一个非0
      let j = -1 // 指向第一个 0，索引未知先设置为-1
    
      for (i = 0; i < length; i++) {
        // 第一个 0
        if (arr[i] === 0) {
          if (j < 0) {
            j = i // j一开始指向第一个0，后面不会执行这里了
          }
        }
    
        // arr[i]不是0的情况
        if (arr[i] !== 0 && j >= 0) {
          // 交换数值
          const n = arr[i] // 临时变量，指向非0的值
          arr[i] = arr[j] // 把arr[j]指向0的值交换给arr[i]
          arr[j] = n // 把arr[i]指向非0的值交换给arr[j]
    
          j++ // 指针向后移动
        }
      }
    }

    // 功能测试
    const arr = [1, 0, 3, 4, 0, 0, 11, 0]
    moveZero2(arr)
    console.log(arr)

    // 性能测试
    
    // 移动 0 到数组的末尾（嵌套循环）
    const arr1 = []
    for (let i = 0; i < 20 * 10000; i++) {
      if (i % 10 === 0) {
        arr1.push(0)
      } else {
        arr1.push(i)
      }
    }
    console.time('moveZero1')
    moveZero1(arr1)
    console.timeEnd('moveZero1') // 262ms
    
    // 移动 0 到数组末尾（双指针）
    const arr2 = []
    for (let i = 0; i < 20 * 10000; i++) {
      if (i % 10 === 0) {
        arr2.push(0)
      } else {
        arr2.push(i)
      }
    }
    console.time('moveZero2')
    moveZero2(arr2)
    console.timeEnd('moveZero2') // 3ms
    
    // 结论：双指针方式优于嵌套循环方式
Last Updated:
Contributors: leeguooooo