BM48. [数据流中的中位数]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM48. 数据流中的中位数
题目中给出的信息：
- 寻找中位数
- 数据在不断增长
传统的寻找中位数的方法便是排序之后，取中间值或者中间两位的平均即可，但是因为数组在不断增长， 每增长一位便排一次，很浪费时间，于是可以考虑在增加数据的同时将其有序化。
方法一：插入排序法
具体做法：
用一vector存储输入的数据流。Insert函数在插入的同时，遍历之前存储在vector中的数据,按照递增顺序依次插入，如此一来，加入的数据流便是有序的，GetMedian函数可以根据下标直接访问中位数,记得需要类型转换为double。
class Solution {
public:
vector<int> val;//记录输入流
void Insert(int num) {
if(val.empty())
val.push_back(num); //val中没有数据，直接加入
else{//val中有数据，需要插入排序
int i = 0;
for(; i < val.size(); i++){//遍历找到插入点
if(num <= val[i]){
break;
}
}
val.insert(val.begin() + i, num);
}
}
double GetMedian() {
int n = val.size();
if(n % 2 == 1){
return double(val[n / 2]); //类型转换
}
else{
double a = val[n / 2];
double b = val[n / 2 - 1];
return (a + b) / 2;
}
}
};
复杂度分析：
- 时间复杂度：Insert函数O(n)，不管遍历还是插入都是O(n)，GetMedian函数O(1)，直接访问
- 空间复杂度：O(n)， 记录输入流的vector
方法二：堆排序
除了插入排序，还可以用堆排序，速度更快，时间复杂度更低。
具体做法：
中位数为一个数列的中间两个或一个，也即中位数将数列分成了较小的部分和较大的部分。我们可以维护两个堆，分别是大顶堆min，用于存储较小的值，其中顶部最大；小顶堆max，用于存储较小的值，其中顶部最小，则中位数只会在两个堆的堆顶出现。我们可以约定奇数时取大顶堆的顶部值，偶数时取两堆顶的平均值，则可以发现两个堆的数据长度要么是相等的，要么奇数时大顶堆会多一个。
每次输入的数据流先进入大顶堆排序，然后将小顶堆的最大值弹入大顶堆中，完成整个的排序。但是因为大顶堆的数据不可能会比小顶堆少一个，因此需要再比较二者的长度，若是小顶堆长度小于大顶堆，需要从大顶堆中弹出最小值到大顶堆中进行平衡。
两个弹出：
第一个是为了遍历整个数列进行排序，要不然只会在大顶堆排
第二个是为了平衡两个堆的数据量，要不然小顶堆会一直增多
class Solution { public: priority_queue<int> min; //大顶堆，元素数值较小 priority_queue<int, vector<int>, greater<int>> max;//小顶堆，元素数值都比大顶堆大 //维护两个堆，取两个堆顶部即可 void Insert(int num) { min.push(num);//先加入较小部分 max.push(min.top()); //将较小部分的最大值取出，送入到较大部分 min.pop(); if(min.size() < max.size()){ //平衡两个堆的数量 min.push(max.top()); max.pop(); } } double GetMedian() { if(min.size() > max.size()) return (double)min.top(); else return (double)(min.top() + max.top()) / 2; } };
复杂度分析
- 时间复杂度：Insert函数O(lgn)，维护堆的复杂度，GetMedian函数O(1)，直接访问
- 空间复杂度：O(n)，两个堆的空间，虽是两个，但是一个堆最多n/2
