【数据结构与算法】(13)：移动0到数组末尾

经典算法题：给出一个数组，要求把数组中所有的 0 移动到数组末尾，要求在原数组上进行操作。

一、问题示例

示例 1：

• 输入：[1,2,0,5,0,7]
• 输出：[1,2,5,7,0,0]

示例 2：

• 输入：[1,0,2,0,0,0,5,7]
• 输出：[1,2,5,7,0,0,0,0]

二、代码演示

1. for + splice 实现

// 移动 0 到数组末尾 for splice

export function moveZero1(arr:number[]):void {
  const len = arr.length;
  if (len === 0) return
  let zeroLen = 0
  for (let i = 0; i < len - zeroLen; i++) {
    if (arr[i] === 0) {
      arr.push(0)
      arr.splice(i, 1) // splice O(n)
      i--
      zeroLen++ // 增加 0 的长度
    }
  }
}

2. for + 双指针 实现

// 移动 0 到数组末尾 for slice

export function moveZero2(arr:number[]):void {
  const len = arr.length
  if (len === 0) return
  let i = 0
  let j = -1

  for (;i < len;i++) {
    if (arr[i] === 0) {
      // 第一个 0
      if (j<0) {
        j = i
      }
    }

    if (arr[i] !== 0 && j >= 0) {
      // 交换
      const n = arr[i]
      arr[i] = arr[j]
      arr[j] = n

      j ++
    }
  }
}

三、单元测试

import { moveZero1, moveZero2 } from '../move-zero.ts'

describe('移动 0 到数组末尾', () => {
  it('正常情况', () => {
    let arr = [0,2,5,0,2,0,0,2,50,0,3]
    moveZero1(arr)
    expect(arr).toEqual([2, 5, 2, 2, 50, 3, 0, 0, 0, 0, 0])
  })
  it('没有 0', () => {
    let arr = [1,2,3,4,6,7]
    moveZero1(arr)
    expect(arr).toEqual([1,2,3,4,6,7])
  })
  it('全是 0', () => {
    let arr = [0,0,0,0,0]
    moveZero1(arr)
    expect(arr).toEqual([0,0,0,0,0])
  })
})

describe('移动 0 到数组末尾', () => {
  it('正常情况', () => {
    let arr = [0,2,5,0,2,0,0,2,50,0,3]
    moveZero2(arr)
    expect(arr).toEqual([2, 5, 2, 2, 50, 3, 0, 0, 0, 0, 0])
  })
  it('没有 0', () => {
    let arr = [1,2,3,4,6,7]
    moveZero2(arr)
    expect(arr).toEqual([1,2,3,4,6,7])
  })
  it('全是 0', () => {
    let arr = [0,0,0,0,0]
    moveZero2(arr)
    expect(arr).toEqual([0,0,0,0,0])
  })
})

四、性能测试

const arr5 = []
for (let i = 0; i < 20 * 10000; i++) {
  if (i % 2 === 0) {
    arr5.push(0)
  } else {
    arr5.push(i)
  }
}
let arr6 = JSON.parse(JSON.stringify(arr5))

console.time('moveZero1')
moveZero1(arr5)
console.timeEnd('moveZero1')

console.time('moveZero2')
moveZero2(arr6)
console.timeEnd('moveZero2')

运行


moveZero1 run time： 0

---

moveZero2 run time： 0

---

五、算法复杂度

方法	时间复杂度
for + splice	O(n^2)
for 双指针	O(n)

---

欢迎访问：天问博客

本文作者： Tiven
发布时间： 2023-07-21
最后更新： 2023-07-24
本文标题： 【数据结构与算法】(13)：移动0到数组末尾
本文链接： https://www.tiven.cn/p/68ab9db6/
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！