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

天问博客

经典算法题：给出一个数组，要求把数组中所有的 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]

二、代码演示

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 的长度
    }
  }
}

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')

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'

}

五、算法复杂度

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

欢迎访问：天问博客

#一、问题示例

#二、代码演示

#三、单元测试

#四、性能测试

#五、算法复杂度

一、问题示例

二、代码演示

三、单元测试

四、性能测试

五、算法复杂度