解析见:数据流中的中位数
/**
* initialize your data structure here.
*/
var MedianFinder = function() {
this.maxHeap = new Heap('max');
this.minHeap = new Heap('min');
this.count = 0;
};
/**
* @param {number} num
* @return {void}
*/
MedianFinder.prototype.addNum = function(num) {
this.count++;
if (this.count % 2 === 1) {
this.maxHeap.add(num);
this.minHeap.add(this.maxHeap.pop());
} else {
this.minHeap.add(num);
this.maxHeap.add(this.minHeap.pop());
}
};
/**
* @return {number}
*/
MedianFinder.prototype.findMedian = function() {
if (this.count === 0) {
return 0;
}
if (this.count % 2 === 1) {
return this.minHeap.value[0];
} else {
return (this.minHeap.value[0] + this.maxHeap.value[0]) / 2
}
};
function Heap(