一、题目描述
二、算法原理
思路：建立大小堆
如果这个数组是有序的，那么把他们的前半部分放到大根堆，后半部分放到小根堆，那么他们的中间值就是如果这两个堆的节点加起来是偶数，那么两个堆顶加起来 / 2 就行，那么如果是奇数那么返回大根堆的堆顶元素就行；
怎么让这两个数组的值是有序的：
1）约定：大根堆的节点数目可以比小根堆的多一个；
2）如果大根堆的节点数目 == 小根堆的节点数目，那么：
如果 ：add 的值 num 大于 大根堆的堆顶，就放到小根堆里面，此时违反了约定，所以把小根堆的堆顶元素入大根堆，然后让小根堆 pop
如果：num <= 大根堆的堆顶元素 || 大根堆为空，那么直接入大根堆
3）如果大根堆的节点数目 > 小根堆的节点数目，那么：
如果：num > 大根堆的堆顶元素，直接入小根堆
如果：num <= 大根堆的堆顶元素，先入大根堆，再把大根堆的堆顶元素入小根堆，再让大根堆 pop
4）不存在大根堆的节点数目 < 小根堆的节点数目，因为上面的 3 条规则使然；
三、代码实现
class MedianFinder { public: MedianFinder() { } void addNum(int num) { if(maxi.size() == mini.size()) { if(maxi.empty() || num <= maxi.top()) maxi.push(num); else { mini.push(num); maxi.push(mini.top()); mini.pop(); } } else if(maxi.size() > mini.size()) { if(num > maxi.top()) mini.push(num); else { maxi.push(num); mini.push(maxi.top()); maxi.pop(); } } //因为上面的判断维持 maxi.size() > mini.size()，所以就不存在 maxi.size() < mini.size() } double findMedian() { if((maxi.size() + mini.size()) % 2 == 0) return ((double)maxi.top() + (double)mini.top()) / 2; else return maxi.top(); } private: priority_queue<int> maxi;//大堆 priority_queue<int,vector<int>,greater<int>> mini; }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */
