?LeetCode刷題實戰(zhàn)295：數(shù)據(jù)流的中位數(shù)
void addNum(int num) - 從數(shù)據(jù)流中添加一個整數(shù)到數(shù)據(jù)結(jié)構(gòu)中。
double findMedian() - 返回目前所有元素的中位數(shù)。
示例
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
進階:
如果數(shù)據(jù)流中所有整數(shù)都在 0 到 100 范圍內(nèi)，你將如何優(yōu)化你的算法？
如果數(shù)據(jù)流中 99% 的整數(shù)都在 0 到 100 范圍內(nèi)，你將如何優(yōu)化你的算法？
解題
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
/*建立兩個堆：（1）一個大根堆，保存所有整數(shù)中較小的1/2;一個小根堆，保存所有整數(shù)中較大的1/2;
（2）并且，依次添加元素過程中，兩個堆大小的差的絕對值不能超過1；*/
//第一元素加入大根堆
if(heap1.size()==0){
heap1.push(num);
return;
}
if(num<=heap1.top()){
//第二個元素比大根堆的頂小
heap1.push(num);
//大根堆元素過多
if(heap1.size()-heap2.size()>1)
{
int temp = heap1.top();
heap1.pop();
heap2.push(temp);//大根堆彈出頂?shù)叫「?
}
}
else{
//第二個元素比大根堆的頂大，直接進入小根堆
heap2.push(num);
//小根堆元素過多
if(heap2.size()-heap1.size()>1)
{
int temp = heap2.top();
heap2.pop();
heap1.push(temp);//小根堆彈出頂?shù)酱蟾?
}
}
}
double findMedian() {
//輸入的元素為奇數(shù)個
if(heap1.size() > heap2.size())
return heap1.top();
else if(heap1.size() < heap2.size())
return heap2.top();
//輸入的元素個數(shù)為偶數(shù)
else
return (heap1.top()+heap2.top())/2.0;
//取大根堆、小根堆的堆頂元素取平均值，即為所求全局中位數(shù)
}
private:
priority_queue<int> heap1;//默認(rèn)，大根堆
priority_queue<int,vector<int>,greater<int>> heap2;//小根堆（升序序列）
};