题目：剑指 Offer 41. 数据流中的中位数 - 力扣（Leetcode）
题目的接口：
class MedianFinder { public: /** initialize your data structure here. */ MedianFinder() { } void addNum(int num) { } double findMedian() { } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */
解题思路：
我的思路是：
通过优先级队列维护一个大堆，一个小堆；
输入数据的时候：
1. 如果两个堆size相同，先进大堆，大堆top再进小堆，维持大堆比小堆小；
2. 如果小堆size大于大堆，先进小堆，小堆top再进大堆，维持大堆比小堆小。
例：
现在两个堆大小相同，
所以2进大堆：
根据我们的思路，
再进小堆：
现在小堆比大堆大，
我们先让3进小堆：
然后，让小堆的top
再进大堆：
现在大堆和小堆又一样大了，
所以，4先进大堆：
然后让大堆的top
再进小堆：
通过观察上面的图解，我们可以清楚的观察到，
大堆和小堆实现了一个动态的平衡状态，
也让中位数的求解变成只需要观察他们的堆顶即可。
查找中位数的时候：
1. 如果小堆size大于大堆，返回小堆堆顶；
2. 如果两个堆size相等，返回两个堆堆顶的值*0.5（中位数）。
代码：
class MedianFinder { public: //建一个大堆 priority_queue, less> max_q; //建一个小堆 priority_queue, greater> min_q; MedianFinder() { } void addNum(int num) { //如果两个堆size相等 if(max_q.size() == min_q.size()) { //先进大堆，大堆top再进小堆，维持大堆比小堆小 max_q.push(num); min_q.push(max_q.top()); max_q.pop(); } else//如果小堆size大于大堆 { //先进小堆，小堆top再进大堆，维持大堆比小堆小 min_q.push(num); max_q.push(min_q.top()); min_q.pop(); } } double findMedian() { //如果小堆size大于大堆，返回小堆堆顶 //如果两个堆size相等，返回两个堆堆顶的值*0.5（中位数） return max_q.size() < min_q.size() ? min_q.top() : (max_q.top() + min_q.top()) * 0.5; } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */
过啦！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
