【数据结构与算法】(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')

<div> <button style='padding: 10px 20px; color: #00b1fb;' class='rotate-btn' onclick='run()'>运行</button> <br> <b>moveZero1 run time：</b> <span style='color: red;' class='box1-ms'>0</span> <hr> <b>moveZero2 run time：</b> <span style='color: red;' class='box2-ms'>0</span> <hr> </div> <script> // 移动 0 到数组末尾 for splice function moveZero1(arr) { 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 的长度 } } }

function moveZero2(arr) { 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 ++
  }
}

}

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

let s1 = performance.now()
moveZero1(arr5)
document.querySelector('.box1-ms').innerText = performance.now() - s1 + ' ms'

let s2 = performance.now()
moveZero2(arr6)
document.querySelector('.box2-ms').innerText = performance.now() - s2 + ' ms'

} </script>

五、算法复杂度

欢迎访问：天问博客