问题描述
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
示例：
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
进阶:
- 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
- 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？
解题思路
方法一：大小堆
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 | class MedianFinder {
public:
/** initialize your data structure here. */
priority_queue<int> left;
priority_queue<int, vector<int>, greater<>> right;
MedianFinder() {
}
void addNum(int num) {
if (left.size() < right.size()) {
right.emplace(num);
left.emplace(right.top());
right.pop();
} else {
left.emplace(num);
right.emplace(left.top());
left.pop();
}
}
double findMedian() {
int sz = left.size() + right.size();
if (sz & 1) return right.top();
return ((double) right.top() + left.top()) / 2;
}
};
|
方法二：multiset 加中位数指针
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 | class MedianFinder {
public:
/** initialize your data structure here. */
multiset<int> nums;
decltype(nums.begin()) mid;
MedianFinder() {
}
void addNum(int num) {
int sz = nums.size();
nums.emplace(num);
if (sz == 0) {
mid = nums.begin();
return ;
}
if (sz & 1) {
if (num >= *mid) ++mid;
} else {
if (num < *mid) --mid;
}
}
double findMedian() {
int sz = nums.size();
return ((double) *mid + *prev(mid, 1 - (sz & 1))) / 2;
}
};
|
方法三：神奇的 Python 切片赋值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.nums = []
def addNum(self, num: int) -> None:
idx = bisect_left(self.nums, num)
self.nums[idx:idx] = [num]
def findMedian(self) -> float:
n = len(self.nums)
return (self.nums[n // 2] + self.nums[(n - 1) // 2]) / 2
|