当前位置: 首页 > news >正文

算法通关村14关 | 数据流中位数问题

1. 数据流中位数问题

题目

 LeetCode295: 中位数是有序列表中间的数,如果列表长度是偶数,中位数是中间两个数的平均值,

例如:[2,3,4]的中位数是3,

[2,3]中位数是(2+3)/ 2= 2.5

设计一个数据结构:

void addNum(int num) 从数据流中添加一个整数到数据结构中

double findMedian()-返回目前所有元素的中位数。

思路

用大顶堆+小顶堆来求解,

小顶堆:存储所有元素中较大的一半,堆顶存储的是其中最小的数

大顶堆:存储所有元素中较小的一半,堆顶存储的是其中最大的数

相当于把元素分为两半,我们计算中位数,只需要小顶堆和大顶堆的根节点即可。

以[1,2,3,4,5]为例,砍成两半后为[1,2]和[3,4,5]我们只要能快速找到2和3即可。

下面看看使用两个堆是怎么变化的

  1. 添加1,进入minHeap中,中位数是1,
  2. 添加2,比民Heap堆顶元素1大,进入minHeap中,同时minHeap中元素超过了所有元素的总和的一半,所以要平衡一下,分一个给maxHeap,中位数是(1+2)/2=1.5.
  3. 添加3,它比minHeap堆顶的元素2大,进入minHeap,中位数为2。
  4. 添加4,比minHeap堆顶的元素2大,进入minHeap,,同时minHeap中元素超过了所有元素的总和的一半,所以要平衡一下,分一个给maxHeap,中位数是(2+3)/2=2.5.
  5. 添加5,它比minHeap堆顶的元素3大,进入minHeap,中位数为3。

代码

public class MediaFinder {//小顶堆存储的是比较大的元素,堆顶是其中的最小值PriorityQueue<Integer> minHeap;//大顶堆存储的是比较大的元素,堆顶是其中的最大值PriorityQueue<Integer> maxHeap;public MediaFinder(){this.minHeap = new PriorityQueue<Integer>();this.maxHeap = new PriorityQueue<Integer>((a, b) -> (b - a));}public void addNum(int num){//小顶堆存储的是比较大的元素,num比较大元素中最小的还大,所以,进入minHeapif (minHeap.isEmpty() || num > minHeap.peek()){minHeap.offer(num);//如果minHeap比maxHeap多两个元素,就平衡if (minHeap.size() - maxHeap.size() > 1){maxHeap.offer(minHeap.poll());}}else {maxHeap.offer(num);//这样可以保证多的那个元素一定在minHeap中if (maxHeap.size() - minHeap.size() > 0){minHeap.offer(maxHeap.poll());}}}public double findMedian(){if (minHeap.size() > maxHeap.size()){return minHeap.peek();} else if (minHeap.size() < maxHeap.size()) {return maxHeap.peek();}else {return (minHeap.peek() + maxHeap.peek())/2.0;}}
}

http://www.lryc.cn/news/154749.html

相关文章:

  • 工厂模式 与 抽象工厂模式 的区别
  • 安装虚拟机+安装/删除镜像
  • MySQL的内置函数复合查询内外连接
  • 操作系统(OS)与系统进程
  • 防重复提交:自定义注解 + 拦截器(HandlerInterceptor)
  • Excel中将文本格式的数值转换为数字
  • uni-app开发小程序中遇到的map地图的点聚合以及polygon划分区域问题
  • 【笔记】软件测试的艺术
  • 配置本地maven
  • C# 按钮的AcceptButton和CancelButton属性
  • SMT贴片制造:专业、现代、智能的未来之选
  • python sqlalchemy db.session 的commit()和colse()对session中的对象的影响
  • python读取图像小工具
  • 【ES6】JavaScript中Reflect
  • Ajax + Promise复习简单小结simple
  • WebDAV之π-Disk派盘 + 小书匠
  • LTE ATTACH流程、PDN流程、PGW地址分配介绍
  • SQL sever中用户管理
  • linux————pxe网络批量装机
  • 处理时延降低24倍,联通云粒数据引擎优化实践
  • 学习MATLAB
  • React 18 对 state 进行保留和重置
  • MySQL之事务与引擎
  • Flink集群常见的监控指标
  • React常见知识点
  • Vue-router路由
  • JVM-CMS
  • 无涯教程-Flutter - Dart简介
  • 如何创建美观的邮件模板并通过qq邮箱的SMTP服务向用户发送
  • 手机无人直播软件在苹果iOS系统中能使用吗?