题目
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[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]
解题
方法一：大顶堆和小顶堆
我们没有必要把所有数据进行排序。只需要保证数据左半边的数都小于右半边的数，那么根据左半边的数的最大值及右半边的数的最小值即可得到中位数。
左手大顶堆，右手小顶堆
class MedianFinder { public: priority_queue<int,vector<int>,less<int>> maxheap; priority_queue<int,vector<int>,greater<int>> minheap; /** initialize your data structure here. */ MedianFinder() { } void addNum(int num) { if(maxheap.size()==minheap.size()){ maxheap.push(num); minheap.push(maxheap.top()); maxheap.pop(); } else{ minheap.push(num); maxheap.push(minheap.top()); minheap.pop(); } } double findMedian() { int maxSize=maxheap.size(),minSize=minheap.size(); int mid1=maxheap.top(),mid2=minheap.top(); return maxSize==minSize?(mid1+mid2)/2.0:mid2; } };
