如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

最开始的思路就是用map或者set存储。习惯写python就想直接用median的key去访问median,但是C++ STL的map或者set没有key这个东西,如果用迭代器那么访问元素复杂度是O(n)

看到很多解法是用两个堆来做,一个最大堆,一个最小堆,一开始不理解。后来发现这样的好处是把数据总体切分为两部分,一部分(最大堆)所有元素都比另一部分(最小堆)小。然后当有新元素需要insert的时候,根据现有元素总数奇偶,决定先压入哪个堆,然后弹出一个元素,弹出元素放入另一个堆。

最后的答案处理,根据元素总数奇偶,决定从两个堆分别取还是从特定的那个取。

class Solution{
public:
void Insert(int num){
if (maxS.size() == minS.size()){
maxS.insert(num);
minS.insert(*maxS.begin());
maxS.erase(maxS.begin());
}
else{
minS.insert(num);
maxS.insert(*minS.begin());
minS.erase(minS.begin());
}
} double GetMedian(){
int num = maxS.size() + minS.size(); double median;
if ((num&1)==1){
median = *minS.begin();
}
else{
median = (*maxS.begin() + *minS.begin()) / 2.0;
}
return median;
}
private:
multiset<int, greater<int> > maxS;
multiset<int, less<int> > minS;
};
05-11 13:38