【剑指OFFER】 41. 数据流中的中位数
发布日期:2021-06-29 19:46:45
浏览次数:2
分类:技术文章
本文共 1495 字,大约阅读时间需要 4 分钟。
题目:如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
例如,
[2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构: void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。示例 1:
输入: [“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”] [[],[1],[2],[],[3],[]] 输出:[null,null,null,1.50000,null,2.00000]示例 2:
输入: [“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”] [[],[2],[],[3],[]] 输出:[null,null,2.00000,null,2.50000]限制:
最多会对 addNum、findMedian 进行 50000 次调用。答案
/*** 用大小堆* 如果数组长度为奇数,中位数是最中间的那个,如果长度为偶数是中间偏左的那个元素* 使用最大堆来存储等于或小于中位数的值,只需poll一次就可弹出当前的中位数,使用最小堆来存储大于中位数的值。* 此外需要保持两个堆平衡,因为我们要获得中位数,所以最大堆的大小将始终等于或比最小堆的大小大1,保持平衡就好*/class MedianFinder { private PriorityQueueminP, maxP; public MedianFinder(){ minP = new PriorityQueue<>(); maxP = new PriorityQueue(Collections.reverseOrder()); } public void addNum(int num){ if(minP.size() != maxP.size()){ minP.add(num);//这个数不一定是较小的一般,所以先加入小顶堆 maxP.add(minP.poll());//再往大顶堆中加入小顶堆出堆的元素 }else{ maxP.add(num); minP.add(maxP.poll()); } } public double findMedian(){ return minP.size() != maxP.size()? minP.peek():(minP.peek() + maxP.peek()) / 2.0; }}/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */
转载地址:https://darkness.blog.csdn.net/article/details/115219746 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月10日 19时52分33秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
IIS 配置 HTTPS
2019-04-30
Task.Factory.StartNew(() =>{})
2019-04-30
WPF内嵌网页的两种方式
2019-04-30
DevOps 什么是 CI/CD?
2019-04-30
Windows服务创建及发布
2019-04-30
windows10 iis浏览wcf报404.3错误
2019-04-30
tsql获取sqlserver某个库下所有表
2019-04-30
在线数据库关系图工具
2019-04-30
ppt thinkcell-Thinkcell: 一款强大的专业图表制作工具
2019-04-30
在线关系图工具
2019-04-30
在外租房子,切记九点
2019-04-30
C#站点检测
2019-04-30
Nginx+IIS简单的部署
2019-04-30
OAuth 2.0 的四种方式
2019-04-30
community framework design
2019-04-30
OAuth2.0流程
2019-04-30
RESTful
2019-04-30
什么是Scrum(一)
2019-04-30
什么是Scrum(二)
2019-04-30
什么是Scrum(三)
2019-04-30