分析
为了高效地获取中位数，使用 两个优先队列（堆） 来维护数据流的有序性：
down 堆（大顶堆）：
up 堆（小顶堆）：
通过以下规则维持堆的平衡和正确性：
- 插入元素：
- 如果当前元素小于或等于
down 堆的堆顶，将其插入 down
- 否则，将其插入
up
- 调整堆的平衡：
- 如果
down 的元素个数比 up 多 2，将 down 堆顶移到 up
- 如果
up 的元素个数比 down 多 1，将 up 堆顶移到 down
- 计算中位数：
- 如果两个堆的元素个数相等，中位数为两个堆顶的平均值；
- 如果
down 堆的元素个数比 up 多 1，中位数为 down 堆顶的值
时间复杂度
- 插入操作：
O(logn) （堆的插入与删除）
- 获取中位数：
O(1)
总体复杂度：O(logn) （单次操作）
空间复杂度
使用两个堆存储所有元素，空间复杂度为 O(n)
C++代码
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
|
class MedianFinder {
public:
// 大顶堆，存储较小的一半元素
std::priority_queue<int> down;
// 小顶堆，存储较大的一半元素
std::priority_queue<int, std::vector<int>, std::greater<int>> up;
MedianFinder() {}
void addNum(int num)
{
// 插入到适当的堆
if (down.empty() || num <= down.top())
down.push(num);
else
up.push(num);
// 调整堆的平衡
if (down.size() == up.size() + 2)
{
int x = down.top();
down.pop();
up.push(x);
}
else if (down.size() + 1 == up.size())
{
int x = up.top();
up.pop();
down.push(x);
}
}
double findMedian()
{
if (down.size() == up.size())
return (down.top() + up.top()) / 2.0;
return down.top();
}
};
|
