295 Find Median from Data Stream(Hard)

1.这道题目要求输出数据流中的中位数，有两个操作，一个是添加元素addNum，另外一个是寻找中位数findMedian。

2.主要思路：

1）建立两个堆，分别为小根堆和大根堆；

2）维持这两个堆的大小相等，或者小根堆比大根堆多一个元素，这样在输出最后结果的时候只需要输出大根堆的堆顶元素或者大根堆与小根堆堆顶元素的平均值即可。

3）根据上面的要求，需要保证小根堆的堆顶>=大根堆的堆顶。

4）下面为示意图，其中a<=b<=c<=d<=maxHeap.top()<=minHeap.top()<=e<=f<=g

a,b,c,d,maxHeap.top(),minHeap.top(),e,f,g
|—-maxHeap—-| Median |—-minHeap—-|

 

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) – Add a integer number from the data stream to the data structure.
• double findMedian() – Return the median of all elements so far.

For example:

add(1)
add(2)
findMedian() -> 1.5
add(3) 
findMedian() -> 2

Credits:
Special thanks to @Louis1992 for adding this problem and creating all test cases.

AC代码：

[c language=”++”]
class MedianFinder {
public:
struct cmpMinHeap{
bool operator()(const int&a, const int&b)
{
return a > b;
}
};
/*
a,b,c,d,maxHeap.top(),minHeap.top(),e,f,g
|—-maxHeap—-| Median |—-minHeap—-|
*/
priority_queue<int, vector<int>, cmpMinHeap> minHeap;//存储大于等于中位数的元素
priority_queue<int> maxHeap;//存储小于等于中位数的元素
// Adds a number into the data structure.
void addNum(int num) {
if (minHeap.size() == maxHeap.size())
{//如果两个堆大小相等，需要插入到minHeap，保证minHeap.size()>=maxHeap.size()
if (minHeap.size() == 0 || num >= maxHeap.top())
{//如果两个堆均为空，或者num大于maxHeap，则直接放到minHeap中
minHeap.push(num);
}
else if (num<maxHeap.top())
{//如果num小于maxHeap.top()，则把maxHeap.top()移到minHeap中，把num放到maxHeap中
minHeap.push(maxHeap.top());
maxHeap.pop();
maxHeap.push(num);
}
}
else
{//肯定是minHeap.size()>maxHeap.size()，所以插入到maxHeap
if (num >= minHeap.top())
{//如果num大于minHeap.top()，则把minHeap.top()移到maxHeap中，把num放到minHeap中
maxHeap.push(minHeap.top());
minHeap.pop();
minHeap.push(num);
}
else
{//直接插入到maxHeap即可
maxHeap.push(num);
}
}
}

// Returns the median of current data stream
double findMedian() {
if (maxHeap.size() == minHeap.size())
{//两个堆相等，即为偶数，输出中间两个数的平均值
double median = maxHeap.top() + minHeap.top();
median /= 2.0;
return median;
}
else//否则，一定是奇数，且minHeap比maxHeap多一个元素，所以输出minHeap.top()
return minHeap.top();
}
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();
[/c]