中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
示例：
addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 复制代码
进阶:
- 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
- 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？
本题和上一题 leetcode-面试题 17.20-连续中值 除了进阶要求之外是完全一致的
sort 排序
本题最简单直接的一种方式就是维护一个数组，存储所有的数字
当需要获取中位数的时候，将数组进行排序
然后根据数组中元素数量的奇偶获取中位数即可
代码如下：
var MedianFinder = function() { this.arr = []; }; /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function(num) { this.arr.push(num); }; /** * @return {number} */ MedianFinder.prototype.findMedian = function() { // 对数组排序 this.arr.sort((a,b) => a-b) // 根据数组长度奇偶返回对应中位数 const len = this.arr.length; if(len%2) return this.arr[len>>1] return (this.arr[(len>>1)-1]+this.arr[len>>1])/2 }; 复制代码
但是这种解题方法每次获取中位数的时候都需要对数组进行排序
而且本题对时间复杂度的限制更高，所以这种解题方式虽然可行，但是提交会超出时间限制
二分插入
为了避免每次对数组进行排序，我们可以将新的整数直接插入到数组的合适位置
这样就能保证数组一直有序，从而避免每次获取中位数的时候再进行排序
代码如下：
// 二分插入 var MedianFinder = function() { this.arr = []; }; /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function(num) { // 每次将num插入到有序数组合适位置，维持数组有序 if(this.arr.length==0||num<=this.arr[0]) this.arr.unshift(num) else if(num>=this.arr[this.arr.length-1]) this.arr.push(num) else{ let l = 0,r = this.arr.length-1; while(l<r){ const mid = (l+r)>>1; if(this.arr[mid]<num) l = mid+1 else r = mid } this.arr.splice(l,0,num) } }; /** * @return {number} */ MedianFinder.prototype.findMedian = function() { // 根据数组长度奇偶返回对应中位数 const len = this.arr.length; if(len%2) return this.arr[len>>1] return (this.arr[(len>>1)-1]+this.arr[len>>1])/2 }; 复制代码
堆
本题获取中位数，其实就是要维护一个前半部分的最大值和后半部分的最小值
维护最值，我们可以通过堆来实现
所以本题还可以通过一个大顶堆，维护前半部分较小值
通过一个小顶堆维护后半部分较大值
维护两个堆中元素数量的差值不大于 1,且大顶堆中元素数量大于等于小顶堆元素数量 这样获取中位数的时候，如果两个堆元素数量相等，则中位数是两个堆顶元素的平均值
否则中位数就是大顶堆堆顶元素值
动画演示如下：
代码如下：
// 堆 class Heap { constructor(compare){ this.arr = []; this.size = 0; this.compare = compare } // 插入操作 push(val){ this.arr.push(val); this.size++; // 插入后自下向上平衡调整 if(this.size>1){ let cur = this.size-1, parent = (cur-1)>>1; while(cur>0&&this.compare(this.arr[parent],this.arr[cur])){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent,parent = (cur-1)>>1; } } } // 弹出操作 pop(){ const res = this.arr[0]; this.arr[0] = this.arr.pop(); this.size--; // 弹出后自上向下平衡调整 let cur = 0, childl = 1,childr = 2; while( (childl<this.size&&this.compare(this.arr[cur],this.arr[childl])) || (childr<this.size&&this.compare(this.arr[cur],this.arr[childr])) ){ if(childr<this.size&&this.compare(this.arr[childl],this.arr[childr])){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]] cur = childl } childl = cur*2+1,childr = cur*2+2; } return res; } // 获取堆顶元素 top(){ return this.arr[0] } } var MedianFinder = function() { // 创建大顶堆，小顶堆实例 this.bigHeap = new Heap((a,b) => a<b) this.littleHeap = new Heap((a,b) => a>b) }; /** * @param {number} num * @return {void} */ MedianFinder.prototype.addNum = function(num) { // 当两个堆为空或者当前值小于等于大顶堆堆顶元素的时候，插入大顶堆 if(this.bigHeap.size===0||num<=this.bigHeap.top()){ this.bigHeap.push(num) // 如果大顶堆元素数量大于小顶堆元素数量+1 // 弹出大顶堆堆顶元素插入小顶堆 if(this.bigHeap.size>this.littleHeap.size+1){ this.littleHeap.push(this.bigHeap.pop()) } }else{ this.littleHeap.push(num) // 如果小顶堆元素数量大于大顶堆 // 弹出小顶堆堆顶元素插入大顶堆 if(this.littleHeap.size>this.bigHeap.size){ this.bigHeap.push(this.littleHeap.pop()) } } }; /** * @return {number} */ MedianFinder.prototype.findMedian = function() { // 如果两堆元素数量相等，中位数是两堆顶元素平均值 if(this.bigHeap.size===this.littleHeap.size){ return (this.bigHeap.top()+this.littleHeap.top())/2 } // 否则中位数是大顶堆堆顶元素 return this.bigHeap.top(); }; 复制代码
最后说一下本题的进阶要求
如果给定的数字都是大于零的整数，那最高效的排序方式就是计数排序
维护数组的过程中，再维护两个指针指向当前中位数，如果数组元素数量为奇数
则两指针指向中间同一个元素
如果数组元素数量为偶数，则两指针指向中间两个元素
如果有 1% 的元素不在 0-100 范围内，则单独维护即可
这也是官方给出的优化题解，但是官方以及其他题解都没有实现对应的代码 而我在实现对应代码的过程中，发现维护两个指针要比想象中还要复杂一些
然后提交后的效率也并不高，和二分插入的方式相仿，但是逻辑和编码的复杂度却更高
而且这种方式也并不是普适的解题方式，所以我个人不太认同，这里也就不展开讲了
至此我们就完成了 leetcode-295-数据流的中位数
如有任何问题或建议，欢迎留言讨论！
