主页 / coding / 问题 / 77592062
Accepted
notaorb
Asked: 2023-12-03 04:26:02 +0800 CST

数组的中位数？跟踪中位数的最佳解决方案[重复]

  • 772

数字是随机生成的并存储到扩展数组中。您如何跟踪中位数？

思路：数组二叉树堆

javascript

1 个回答

  1. Best Answer

    一般来说，编程有很多种选择，但由于我们使用的是 JS，所以最简单的方法就是简单地保留一个数组并按排序顺序插入元素，例如：

    class Median {
  arr = []
  insert(i) {
    let l = 0,
      r = this.arr.length
    while (l < r) {
      const m = (l + r) >>> 1
      if (this.arr[m] < i) l = m + 1
      else r = m
    }
    this.arr.splice(l, 0, i)
  }
  get median() {
    const mid = (this.arr.length / 2) | 0
    return this.arr.length ?
      this.arr[mid] : (this.arr[mid - 1] + this.arr[mid]) / 2
  }
}

const m = new Median;
[2, 8, 8, -2, 19].forEach(m.insert.bind(m))
console.log(m.median)

    • 1

相关问题