295. Find Median from Data Stream

Leetcode link

题目简介

var MedianFinder = function() {};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {};

题目要求我们实现三个方法，来随时取出一个数据流中的中位数

解题思路

中位数的本质是我们要找到一个地方其左右两边的数个数相等

第一种想法是我们可以用两个数组来保存 “比当前中位数小的数” 以及 “比当前中位数大的数”

但是这种想法会导致我们在插入过程需要大量的排序操作

所以我们换一种数据结构，使用堆来做

具体来说就是用大顶堆来保存比当前中位数小的元素；用小顶堆来表示比当前中位数大的元素

只要我们维持好两个堆的元素数量相差小于 2，我们就可以断定：中位数必在大顶堆或者小顶堆堆顶之间产生

Javascript

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

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function (num) {
    const peak = this.maxHeap.front()
    if(peak && num > peak) {
        this.minHeap.enqueue(num)
    } else {
        this.maxHeap.enqueue(num)
    }

    const maxHeapSize = this.maxHeap.size()
    const minHeapSize = this.minHeap.size()

    if(minHeapSize - maxHeapSize > 1) {
        this.maxHeap.enqueue(this.minHeap.dequeue())
    } else if(maxHeapSize - minHeapSize > 1) {
        this.minHeap.enqueue(this.maxHeap.dequeue())
    }
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function () {
    const maxHeapSize = this.maxHeap.size()
    const minHeapSize = this.minHeap.size()
    if(maxHeapSize === minHeapSize) {
        return (this.maxHeap.front() + this.minHeap.front()) / 2
    } else if(maxHeapSize > minHeapSize){
        return this.maxHeap.front()
    } else {
        return this.minHeap.front()
    }
};

/** 
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */