Leetcode 295

题目要求

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。

• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

• double findMedian() 返回到目前为止所有元素的中位数。

核心算法和原理

• 最大堆装前一半数，最小堆装后一半数（前者元素数量可以多一个）

• 每次加入新的元素时，至多破坏一个元素的所属关系（属于前一半还是后一半），并且这个元素一定是两个堆的堆顶之一

• 判断关系十分简单，比较堆顶即可，如代码所示

代码

class MedianFinder {
    priority_queue<int, vector<int>, less<int>> smaller;
    priority_queue<int, vector<int>, greater<int>> larger;
public:
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        int m = smaller.size(), n = larger.size();
        if (m == 0) {
            smaller.push(num);
        } else if (m == n) {
            // put left
            int rightTop = larger.top();
            if (num > rightTop) {
                larger.pop();
                larger.push(num);
                smaller.push(rightTop);
            } else {
                smaller.push(num);
            }
        } else {
            // put right
            int leftTop = smaller.top();
            if (num < leftTop) {
                smaller.pop();
                smaller.push(num);
                larger.push(leftTop);
            } else {
                larger.push(num);
            }
        }
    }
    
    double findMedian() {
        if (smaller.size() == larger.size()) {
            return (smaller.top() + larger.top()) / 2.0;
        } else {
            return (double)smaller.top();
        }
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */