【剑指offer】_18 数据流中的中位数
程序员文章站
2022-07-15 08:26:00
...
题目描述
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。
解题思路
一般数据流我们用数组来表示,要得到中位数有很多种方法,这里介绍一种时间复杂度较小的方法,用C++种的优先级队列。
也就是剑指offer书上的方法,把数组逻辑上分成两个部分,左边为最大堆,右边为最小堆。我们始终要保证最大堆中最大的元素要小于最小堆中最小的元素即可,当然除此之外,还要判断数组中元素个数是偶数还是奇数,如果要判断我们必须要让两个堆中的元素个数之差不大于1,在这里,我们保证最大堆的元素个数可以等于最小堆元素个数+1,但是最小堆堆元素个数最多只能与最大堆相同。 那么如果两个堆的元素个数相同,那么就是偶数,那么中位数就是两个堆顶元素之和除以2,如果不相同的话,说明最大堆的元素个数多,取最大堆堆顶元素即可。
代码实现
class Solution {
priority_queue<int,vector<int>,less<int>> max;
priority_queue<int,vector<int>,greater<int>> min;
public:
void Insert(int num)
{
if(max.empty() || num<= max.top())
max.push(num);
else
min.push(num);
//保证两个堆的元素个数之差小于1
if(max.size() == min.size()+2)
{
min.push(max.top());
max.pop();
}
if(max.size()+1 == min.size())
{
max.push(min.top());
min.pop();
}
}
double GetMedian()
{
return max.size() == min.size() ? (max.top()+min.top())/2.0 : max.top();
}
};
上一篇: 关于Map的作业
推荐阅读
-
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指offer28:找出数组中超过一半的数字。
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
C#版剑指Offer-001二维数组中的查找
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
剑指offer JZ31 整数中1出现的次数 Python 解
-
剑指offer JZ54 字符流中第一个不重复的字符 Python 多解
-
[算法练习-剑指offer]题18.二叉树的镜像(Java)
-
剑指Offer积累-JZ1-二维数组中的查找
-
剑指offer之队列中的最大值(C++/Java双重实现)