本文共 1704 字，大约阅读时间需要 5 分钟。
剑指 Offer 41. 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。 例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构：void addNum(int num) - 从数据流中添加一个整数到数据结构中。double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"][[],[1],[2],[],[3],[]]输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入：["MedianFinder","addNum","findMedian","addNum","findMedian"][[],[2],[],[3],[]]输出：[null,null,2.00000,null,2.50000]
采用两个堆，一个大顶堆来保存元素较小的一半，一个小顶堆保存元素较大的一半，当元素个数总共为偶数个时，大顶堆元素和小顶堆元素各为N/2个，当元素个数总共为计数时，大顶堆元素为N-1/2,小顶堆元素为N+1/2，即始终保持小顶堆元素个数大于等于大顶堆元素个数。为保持这个条件，当两堆元素个数相等时，往小顶堆里插入元素，两堆元素不等时，一定是小顶堆元素多，所以往大顶堆插入元素。但同时为了保持小顶堆里的元素为较大的一半，所以往小顶堆插入元素时，先将元素插入大顶堆，然后取出大顶堆的堆顶元素，往大顶堆插入元素时同理，这样能保证将总元素分为较大一半和较小一半。
class MedianFinder41 { public: priority_queue ,greater >BigHalf; //小顶堆，保存较大的一半 priority_queue SmallHalf; //大顶堆，保存较小的一半 /** initialize your data structure here. */ MedianFinder41() { } void addNum(int num) { //这种添加方式保持存大值的堆的数量总是大于或等于存小值的数量 if(BigHalf.size() != SmallHalf.size()) { BigHalf.push(num); SmallHalf.push(BigHalf.top()); BigHalf.pop(); } else { SmallHalf.push(num); BigHalf.push(SmallHalf.top()); SmallHalf.pop(); } } double findMedian() { if(BigHalf.size() == SmallHalf.size()) { return (BigHalf.top()+SmallHalf.top())/2.0; } else { return BigHalf.top(); } return BigHalf.top(); } }; 转载地址：http://kssqf.baihongyu.com/