题意：有n个操作，存入数字，和输出中位数
题解：要确保输入数字的操作和输出中位数的操作，都是低于等于Log(n)的效率。 那么怎么做呢？我们维护两个multiset ，内部是一棵红黑树。一个树A 维护的是较大值，树B维护的是较小值。A,B平分秋色。 中位数显然就是A里的最小值和B里的最大值中选择。那么在存数字的时候判断这个数字应该放到哪个树里，然后再需要判断A,B的元素数量差，如果出现差值大于1，就要把较多的那个树的某个极值元素放到较小的那个树里，始终保持两个树的元素数量差不超过1，所以存入数字的效率是O(logn*3) 而取中位数是O(1)的效率 不知道为什么multiset的size()函数，会超时，难道是O(n)的效率取size吗？介绍里明明是constant的时间复杂度啊。 用优先队列也可以的。效率是一样的。
代码语言：javascript复制class MedianFinder {
public:
/** initialize your data structure here. */
multiset<int> m1;
multiset<int> m2;
int n=0;
int len1;
int len2;
MedianFinder() {
m1.clear();
m2.clear();
len1=0;
len2=0;
}
void addNum(int num) {
if(len1==0&&len2==0)
{
m1.insert(num);
len1 ;
n ;
return;
}
multiset<int>::iterator it = prev(m1.end());
if(num < *it)
{
m1.insert(num);
len1 ;
}
else
{
m2.insert(num);
len2 ;
}
if(len1<len2-1)
{
m1.insert(*m2.begin());
len1 ;
m2.erase(m2.begin());
len2--;
}
if(len1-1>len2)
{
m2.insert(*prev(m1.end()));
len2 ;
m1.erase(prev(m1.end()));
len1--;
}
n ;
}
double findMedian() {
if(n&1)
{
if(len1<len2)
return *m2.begin();
else
return *prev(m1.end());
}
else
return 1.0*(*prev(m1.end()) *m2.begin())/2;
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
