标题:
如何得到一个数据流中的中位数？如果从数据流中读取奇数个值，则中值是所有值排序后位于中间的值。如果从数据流中读取偶数个值，则中位数是所有值排序后中间两个数字的平均值。
举个例子，
[2，3，4]的中位数是3
[2，3]的中位数是(2 ^ 3)/2 = 2.5。
设计支持以下两种操作的数据结构:
1.void addNum(int num)-将数据流中的整数添加到数据结构中。
2.double find median()-返回当前所有元素的中值。
示例:
输入:
["MedianFinder "，" addNum "，" addNum "，" findMedian "，" addNum "，" findMedian"]
[[],[1],[2],[],[3],[]]
输出:[空，空，空，1.50000，空，2.00000]
想法:
将数组分成两部分。之一部分的更大值和第二部分的最小值是求中位数所需的元素。
你可以维护两个堆:之一部分数据是大堆，第二部分数据是小堆。
在遍历数组的过程中，会维护这两个堆:
1.如果当前元素小于大顶堆，则插入大顶堆；
2.如果两个堆之间的大小差被检查为1，则元素在两个堆之间迁移；
遍历数组后，计算两个堆的中值:
如果两个堆的大小相同，则中位数=两个堆的顶部元素之和/2。
如果两个堆的大小不同，则取堆中编号较大的顶部元素。
代码:
class MedianFinder {public: /** initialize your data structure here. */ MedianFinder() { } void addNum(int num) { if(!lq.empty()本文地址：百科生活频道 https://www.neebe.cn/live/947427.html，易企推百科一个免费的知识分享平台，本站部分文章来网络分享，本着互联网分享的精神，如有涉及到您的权益，请联系我们删除，谢谢！
相关阅读
