题目描述：
寻找数据流中的中位数，奇数时是中间值，偶数时是平均值。
数据范围：最多调用 $5\times 10^4$
题解：
使用两个堆，一个表示小于等于中位数的leMedin，一个表示大于中位数的gtMedin。保证 leMedin.size() 和 gtMedin.size()最多相差 $1$ ，即 leMedin.size() - gtMedin.size() <= 1。这样的话奇数个数就直接取 leMedin.top()，偶数的话求 leMedin,gtMedin的 top()的平均值。
加入数值时，维护两个堆，如果leMedin为空或者小于等于中位数，直接加入 leMedin，这时他的容量可能超了，需要判断是否需要把最大的拿出来加入另一个堆；大于中位数时同理。
需要注意 leMedin维护大顶堆（默认就是大顶堆），gtMedin维护小顶堆（需要使用 greater<int>）。
也可以使用多重集解决，但是 c++多重集无法直接取下标，超时。可以使用 python多重集。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class MedianFinder
{
public:
priority_queue<int> leMedin;
priority_queue<int, vector<int>, greater<int>> gtMedin;
double curMedin;
MedianFinder()
{
}
void addNum(int num)
{
if (leMedin.empty() || num <= curMedin)
{
leMedin.push(num);
if (leMedin.size() - gtMedin.size() > 1)
{
gtMedin.push(leMedin.top());
leMedin.pop();
}
}
else
{
gtMedin.push(num);
if (gtMedin.size() - leMedin.size() >= 1)
{
leMedin.push(gtMedin.top());
gtMedin.pop();
}
}
if (leMedin.size() == gtMedin.size())
curMedin = (leMedin.top() + gtMedin.top()) / 2.0;
else
curMedin = leMedin.top();
}
double findMedian()
{
return curMedin;
}
};
|