中位数 Median 即中数，是有序序列中处于中间位置的数，求解数据库及数据流中的中位数。

众数、中位数、平均数的区别 众数、中位数、平均数都用来描述数据的集中趋势

中位数：有序序列，中间位置的数

• 若是偶数，中间位置的两个数，取平均值
• 不受极小值和极大值的影响

众数：出现频次最高的数

• 计算简便，可以没有，或有多个
• 不受极小值和极大值的影响

平均数：算数平局数 = 总数 / 个数

• 受极小值和极大值影响

例题

571. 给定数字的频率查询中位数

Numbers 表： +-------------+------+ | Column Name | Type | +-------------+------+ | num | int | | frequency | int | +-------------+------+ num 是这张表的主键。这张表的每一行表示某个数字在该数据库中的出现频率。 中位数 是将数据样本中半数较高值和半数较低值分隔开的值。 编写一个 SQL 查询，解压 Numbers 表，报告数据库中所有数字的 中位数 。结果四舍五入至 一位小数 。 查询结果如下例所示。 输入： Numbers 表： +-----+-----------+ | num | frequency | +-----+-----------+ | 0 | 7 | | 1 | 1 | | 2 | 3 | | 3 | 1 | +-----+-----------+ 输出： +--------+ | median | +--------+ | 0.0 | +--------+ 解释： 如果解压这个 Numbers 表，可以得到 [0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3] ，所以中位数是 (0 + 0) / 2 = 0 。

答案

1. SQL 中的聚合函数和开窗函数

• 聚合函数包括：SUM() COUNT() AVG() MAX() MIN()
• 聚合函数搭配 OVER() 开窗函数使用
  • 不会改变记录条数
• 聚合函数搭配 GROUP BY 使用
  • 会改变记录条数

2. 按某一列，升序和降序 排列，逐行累加频次
3. 两次排列中，当前累加频次都 > 总频次一半的行即解

SElECT AVG(num) as median FROM (
  SElECT num, 
  SUM(frequency) OVER (ORDER BY num) AS sum_asc, 
  SUM(frequency) OVER (ORDER BY num DESC) AS sum_desc, 
  SUM(frequency) OVER () AS sum
  FROM Numbers
) tmp WHERE sum_asc >= sum / 2 AND sum_desc >= sum / 2

剑指 Offer 41. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。 例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构： void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。

答案

先放入哪个队列，都没有关系，只需要

• 偶数时，先放入哪个优先队列，奇数时，取这个队列即可

var MedianFinder = function() {
  this.minHeap = new PriorityQueue([], (a, b) => a - b)
  this.maxHeap = new PriorityQueue([], (a, b) => b - a)
};

MedianFinder.prototype.addNum = function(num) {
  if (this.maxHeap.size === this.minHeap.size) {
    this.minHeap.push(this.maxHeap.push(num).pop())
  } else {
    this.maxHeap.push(this.minHeap.push(num).pop())
  }
};

MedianFinder.prototype.findMedian = function() {
  if (this.maxHeap.size === this.minHeap.size) {
    return (this.maxHeap.top() + this.minHeap.top()) / 2
  } else {
    return this.minHeap.top()
  }
}; 

JavaScript 优先队列模板（原创）

class PriorityQueue {
  constructor (ar = [], compare = (a, b) => a - b) {
    this.heap = []
    this.size = 0
    this.compare = compare
    while (ar.length) this.push(ar.pop())
  }

  swap (a, b) {
    const tmp = this.heap[a]
    this.heap[a] = this.heap[b]
    this.heap[b] = tmp
  }

  getParentIndex (index) {
    return index - 1 >> 1
  }

  getLeftIndex (index) {
    return (index << 1) + 1
  }

  getRightIndex (index) {
    return (index << 1) + 2
  }

  shiftUp (index) {
    const paretIndex = this.getParentIndex(index)
    if (this.compare(this.heap[paretIndex], this.heap[index]) > 0) {
      this.swap(paretIndex, index)
      this.shiftUp(paretIndex)
    }
  }

  shiftDown (index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if (this.compare(this.heap[index], this.heap[leftIndex]) > 0) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }
    if (this.compare(this.heap[index], this.heap[rightIndex]) > 0) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }

  push (value) {
    this.heap.push(value)
    this.shiftUp(this.size++)
    return this
  }

  top () {
    return this.heap[0]
  }

  pop () {
    if (this.size === 0) return null
    if (--this.size === 0) return this.heap.pop()
    const top = this.top()
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
    return top
  }

  isEmpty () {
    return this.size === 0
  }
}