题目
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
方法
方法：双堆方法
参考：https://www.cnblogs.com/easonliu/p/4441916.html
时间复杂度：nlogn，比常规的n^2小
思路
对于数据流，就需要在线算法，每次插入新的数据都需要对整个数组进行调整
题目需要找出数据流的中位数，简单的办法就是一个数组存放数据流，每进入一个数，就插入到相应的位置，保持数组的升序，这样的方法复杂度在n^2
可以使用两个堆，分别存放一半的数据，来实现快速查找中位数的效果。
假设有n个数据，一个最大堆，存放小的n/2个数据；一个最小堆，存放大的n/2个数据。当需要获取n个数的中位数的时候，如果n是奇数，直接取最小堆的堆顶；如果是偶数，则取两个堆的堆顶的平均值
在这个方法中，有2个点需要注意：
第一点：如何保证最大堆和最小堆的数据数量平衡？在插入某个数据的时候，判断一下当前n是奇数或者偶数，插入到不同的堆中的即可。这里，当n是奇数的时候，我插入到最大堆中，反之插入最小堆
第二点：如何保证最大堆的所有数据都比最小堆的所有数据小？在第一点的基础上，在插入最大堆之前，判断该数是否比最小堆的堆顶大，是则先将该数插入到最小堆中，然后将最小堆的堆顶拿出，插入到最大堆中，这样就可以保证插入最大堆一定小于最小堆；同理，插入最小堆之前，也做类似判断
注意：
因为此题的关键，在于对堆的应用，而c++的vector有现成的堆排序库函数可以使用，这里我就直接使用c++完成本题代码，而不用js重写堆排序和堆插入等操作
代码
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 Solution {
private:
vector<int> min;
vector<int> max;
public:
void Insert(int num) {
if (max.size() + min.size() & 1) {
if (min.size() > 0 && num > min[0]) {
min.push_back(num);
push_heap(min.begin(), min.end(), greater<int>());
num = min[0];
pop_heap(min.begin(), min.end(), greater<int>());
min.pop_back();
}
max.push_back(num);
push_heap(max.begin(), max.end(), less<int>());
} else {
if (max.size() > 0 && num < max[0]) {
max.push_back(num);
push_heap(max.begin(), max.end(), less<int>());
num = max[0];
pop_heap(max.begin(), max.end(), less<int>());
max.pop_back();
}
min.push_back(num);
push_heap(min.begin(), min.end(), greater<int>());
}
}
double GetMedian() {
if (max.size() + min.size() & 1) {
return min[0];
} else {
return (max[0] + min[0]) * 1.0 / 2;
}
}
};
|
