剣指Offer(41)データストリームの中位数
6648 ワード
トピックでは、データ・ストリームの中位数をどのように取得するかを説明します.データストリームから奇数個の数値を読み出すと、中位数は、すべての数値がソートされた後に中間に位置する数値である.データストリームから偶数個の数値が読み出されると、中位数は、すべての数値が並べ替えられた後の中間の2つの数の平均値となります.アルゴリズム:スタックアルゴリズム データ構造:最大 プログラミング言語:C++
1：
class Solution {
public:
void Insert(int num)
{
if(((min.size()+max.size())&1)==0)
{
if(max.size()>0&&num<max[0])// ，
{
max.push_back(num);
push_heap(max.begin(),max.end(),less<int>());
num=max[0];
pop_heap(max.begin(),max.end(),less<int>());
max.pop_back();
}
min.push_back(num);
push_heap(min.begin(),min.end(),greater<int>());
}
else
{
if(min.size()>0&&num>min[0])// ，
{
min.push_back(num);
push_heap(min.begin(),min.end(),greater<int>());
num=min[0];
pop_heap(min.begin(),min.end(),greater<int>());
min.pop_back();
}
max.push_back(num);
push_heap(max.begin(),max.end(),less<int>());
}
}
double GetMedian()
{
int size=min.size()+max.size();
if(size==0)
return -1.0;
double mid=0.0;
if((size&1)==1)
mid=min[0];
else
mid=((double)(min[0]+(double)max[0])/2);
return mid;
}
private:
vector<int> min;
vector<int> max;
}; 2：
class Solution {
//
priority_queue<int, vector<int>, less<int> > min;
priority_queue<int, vector<int>, greater<int> > max;
public:
void Insert(int num){
//
if(min.empty() || num <= min.top()) min.push(num);
else max.push(num);
if(min.size() == max.size() + 2) max.push(min.top()), min.pop();
if(min.size() + 1 == max.size()) min.push(max.top()), max.pop();
}
double GetMedian(){
return min.size() == max.size() ? (min.top() + max.top()) / 2.0 : min.top();
}
};