力扣295. 数据流的中位数(java,堆解法)
Problem: 295. 数据流的中位数
文章目录
- 题目描述
- 思路
- 解题方法
- 复杂度
- Code
题目描述


思路
由于该题目的数据是动态的我们可以维护两个堆来解决该问题
1.维护一个大顶堆,一个小顶堆
2.每个堆中元素个数接近n/2;如果n是偶数,两个堆中的数据个数都是n/2;如果n是奇数,则大顶堆中有n/2 + 1个数据,小顶堆中有n/2个数据
3.大顶堆中的数据值都要小于小顶堆中的数据值
即大顶堆中的堆顶元素就是中位数
解题方法
1.(创建堆)按思路创建一个大顶堆和小顶堆
2.(维护堆):2.1.如果新插入数据小于等于大顶堆,则将其插入到大顶堆中,否则插入到小顶堆;
2.2.插入数据后,两个堆中的数据量个数不满足思路中的要求2,则我们需要从一个堆中不停的将堆顶元素移动到另一个堆

复杂度
时间复杂度:
a d d N u m : O ( l o g n ) addNum:O(logn) addNum:O(logn)
f i n d M e d i a n : O ( 1 ) findMedian:O(1) findMedian:O(1)
空间复杂度:
O ( n ) O(n) O(n)
Code
class MedianFinder {/*维护一个大顶堆和小顶堆*/private PriorityQueue<Integer> minQueue = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}});private PriorityQueue<Integer> maxQueue = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});public MedianFinder() {}/*** 数据流插入数据** @param num 待插入的数据*/public void addNum(int num) {//如果插入数据小于等于大顶堆堆顶元素,大顶堆直接插入if (maxQueue.isEmpty() || num <= maxQueue.peek()) {maxQueue.add(num);} else {minQueue.add(num);}//大顶堆数据量不能小于小顶堆while (maxQueue.size() < minQueue.size()) {Integer minQueueElement = minQueue.poll();maxQueue.add(minQueueElement);}//小顶堆数据量可以比大顶堆小一个while (minQueue.size() < maxQueue.size() - 1) {Integer maxQueueElement = maxQueue.poll();minQueue.add(maxQueueElement);}}/*** 找出中位数** @return double*/public double findMedian() {//如果大顶堆数据量大于小顶堆if (maxQueue.size() > minQueue.size()) {return maxQueue.peek();} else {return (maxQueue.peek() + minQueue.peek()) / 2f;}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/
相关文章:
力扣295. 数据流的中位数(java,堆解法)
Problem: 295. 数据流的中位数 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路 由于该题目的数据是动态的我们可以维护两个堆来解决该问题 1.维护一个大顶堆,一个小顶堆 2.每个堆中元素个数接近n/2;如果n是偶数,两个堆中的数据个数…...
open3d-点云及其操作
open3d提供了一个专门用于点云的数据结构 PointCloud。 class PointCloud(Geometry3D):color # 颜色normals # 法向量points # 点云def __init__(self, *args, **kwargs):"""__init__(*args, **kwargs)Overloaded function.1. __init__(self: open3d.cpu.py…...
无人机助力电力设备螺母缺销智能检测识别,python基于YOLOv7开发构建电力设备螺母缺销高分辨率图像小目标检测系统
传统作业场景下电力设备的运维和维护都是人工来完成的,随着现代技术科技手段的不断发展,基于无人机航拍飞行的自动智能化电力设备问题检测成为了一种可行的手段,本文的核心内容就是基于YOLOv7来开发构建电力设备螺母缺销检测识别系统…...
如何使用Python的Open3D开源库进行三维数据处理
简介 在本文中,我提供了一个关于如何使用Python的Open3D库(一个用于3D数据处理的开源库)来探索、处理和可视化3D模型的快速演练。 使用Open3D可视化的3D模型(链接https://sketchfab.com/3d-models/tesla-model-s-plaid-9de8855fa…...
HarmonyOS应用开发者基础认证试题
判断题 1.Ability是系统调度应用的最小单元,是能够完成一个独立功能的组件。一个应用可以包含一个或多个Ability。(true) 2.Tabs组件仅可包含子组件TabsContent,每一个页签对应一个内容视图即TabContet组件。(true) 3.使用http模块发起网络请求时&#…...
Android Camera2开启电子防抖(EIS)和光学防抖(OIS)
刚好当前项目有录像功能,使用了第三方框架是基于Camera2引擎开发,当使用 Camera2 API 开发相机应用时,启用和关闭 EIS(电子防抖)是一个重要的功能。EIS 可以帮助减少相机拍摄时的抖动,从而提高图像和视频的…...
劲爆:Sam Altman 回归CEO专访确认Q*的存在
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
Electronica慕尼黑电子展 Samtec团队与21ic分享虎家产品与方案
【摘要/前言】 “希望但凡是能够使用到连接器的场合都有Samtec的身影” 在慕尼黑上海电子展现场,Samtec华东区销售经理章桢彦先生在与21ic副主编刘岩轩老师的采访中,如是说道。这是一种愿景,更是Samtec的努力方向。短短一句话,…...
Vue基本使用(一)
📑前言 本文主要是【Vue】——Vue基本使用的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是听风与他🥇 ☁️博客首页:CSDN主页听风与他 🌄每日一句&#x…...
Android:BackStackRecord
BackStackRecord:fragment回退栈,继承自FragmentTransaction,并且实现了OpGenerator接口,OpGenerator接口用来添加或弹出事务的,后面会提到。 从《Android:从源码看FragmentManager如何工作》文章知道,每次beginTransaction会创建一个BackStackRecord对象,改对象持有f…...
微信小程序 slider 翻转最大和最小值
微信小程序 slider 翻转最大和最小值 场景代码示例index.wxmlindex.jsutil.js 参考资料 场景 我想使用 slider 时最左边是 10 最右是 -10。 但是想当然的直接改成<slider min"10" max"-10" step"1" /> 并没用。 查了文档和社区也没有现成…...
APITable免费开源的多维表格与可视化数据库本地部署公网远程访问
APITable免费开源的多维表格与可视化数据库公网远程访问 文章目录 APITable免费开源的多维表格与可视化数据库公网远程访问前言1. 部署APITable2. cpolar的安装和注册3. 配置APITable公网访问地址4. 固定APITable公网地址 前言 vika维格表作为新一代数据生产力平台,…...
配电房综合监控系统
配电房综合监控系统是一种集成了实时监控、数据采集、远程控制等多功能的系统,用于对配电房进行全方位的监测和管理。 力安科技配电室综合监控系统依托电易云-智慧电力物联网,实现配电室环境监测、有害气体监测、安防监控、采暖通风、门禁、灯光、风机、…...
【JavaSE】集合(学习笔记)
一、数据结构 1、栈 压栈 / 弹栈栈顶元素、栈底元素先进后出 2、队列 入队列 / 出队列前端、后端先进先出 3、数组 查询效率高,增删效率低 4、链表 查询效率低(必须从头找),增删效率高 5、哈希表 比较方法哈希值equals结构:数组 链…...
Mybatis 的简单运用介绍
Mybatis 用于操作数据库 操作数据库肯定需要: 1.SQL语句 2.数据库对象和 java 对象的映射 接下来我们看看怎么使用 Mybatis 我们先搞一些数据库内容 然后将其这些内容和Java对象进行映射 再创建一个类实现 select * from 再写一个类证明上述代码是否可以实现 别忘了在appli…...
python的itertools库
itertools常用的方法如下: import itertools 1. 生成的列表累加,在生成新的列表x itertools.accumulate(range(10))print(list(x))结果:[0, 1, 3, 6, 10, 15, 21, 28, 36, 45] 2. 连接多个列表或者迭代器x itertools.chain(range(3), rang…...
STM32/GD32_分散加载
Q:如何将一个变量、某个源文件的函数在编译阶段就存储在用户指定的区域? KEIL环境:.map后缀文件、.sct后缀文件 IAR环境:.map后缀文件、.icf后缀文件 【map文件】 对固件里面的变量、函数、常量等元素的存储空间进行分配的说明…...
go clean
移除目标文件和缓存文件。 更多信息:https://golang.org/cmd/go/#hdr-Remove_object_files_and_cached_files. 只打印移除命令,而不会真正移除任何东西: go clean -n 删除编译缓存: go clean -cache 删除所有测试结果缓存&…...
BUUCTF [ACTF新生赛2020]swp 1
BUUCTF:https://buuoj.cn/challenges 题目描述: 得到的 flag 请包上 flag{} 提交。 密文: 下载附件,得到一个.tar文件。 解题思路: 1、使用WinRAR解压.tar文件,得到两个.zip文件。 解压wget.zip文件,得…...
【PTA题目】7-4 缩写期刊名 分数 10
7-4 缩写期刊名 分数 10 全屏浏览题目 切换布局 作者 黄龙军 单位 绍兴文理学院 科研工作者经常要向不同的期刊投稿。但不同期刊的参考文献的格式往往各不相同。有些期刊要求参考文献所发表的期刊名必须采用缩写形式,否则直接拒稿。现对于给定的期刊名ÿ…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
