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

力扣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,则我们需要从一个堆中不停的将堆顶元素移动到另一个堆

image.png

复杂度

时间复杂度:

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.维护一个大顶堆&#xff0c;一个小顶堆 2.每个堆中元素个数接近n/2&#xff1b;如果n是偶数&#xff0c;两个堆中的数据个数…...

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开发构建电力设备螺母缺销高分辨率图像小目标检测系统

传统作业场景下电力设备的运维和维护都是人工来完成的&#xff0c;随着现代技术科技手段的不断发展&#xff0c;基于无人机航拍飞行的自动智能化电力设备问题检测成为了一种可行的手段&#xff0c;本文的核心内容就是基于YOLOv7来开发构建电力设备螺母缺销检测识别系统&#xf…...

如何使用Python的Open3D开源库进行三维数据处理

简介 在本文中&#xff0c;我提供了一个关于如何使用Python的Open3D库&#xff08;一个用于3D数据处理的开源库&#xff09;来探索、处理和可视化3D模型的快速演练。 使用Open3D可视化的3D模型&#xff08;链接https://sketchfab.com/3d-models/tesla-model-s-plaid-9de8855fa…...

HarmonyOS应用开发者基础认证试题

判断题 1.Ability是系统调度应用的最小单元&#xff0c;是能够完成一个独立功能的组件。一个应用可以包含一个或多个Ability。(true) 2.Tabs组件仅可包含子组件TabsContent&#xff0c;每一个页签对应一个内容视图即TabContet组件。(true) 3.使用http模块发起网络请求时&#…...

Android Camera2开启电子防抖(EIS)和光学防抖(OIS)

刚好当前项目有录像功能&#xff0c;使用了第三方框架是基于Camera2引擎开发&#xff0c;当使用 Camera2 API 开发相机应用时&#xff0c;启用和关闭 EIS&#xff08;电子防抖&#xff09;是一个重要的功能。EIS 可以帮助减少相机拍摄时的抖动&#xff0c;从而提高图像和视频的…...

劲爆:Sam Altman 回归CEO专访确认Q*的存在

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

Electronica慕尼黑电子展 Samtec团队与21ic分享虎家产品与方案

【摘要/前言】 “希望但凡是能够使用到连接器的场合都有Samtec的身影” 在慕尼黑上海电子展现场&#xff0c;Samtec华东区销售经理章桢彦先生在与21ic副主编刘岩轩老师的采访中&#xff0c;如是说道。这是一种愿景&#xff0c;更是Samtec的努力方向。短短一句话&#xff0c;…...

Vue基本使用(一)

&#x1f4d1;前言 本文主要是【Vue】——Vue基本使用的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是听风与他&#x1f947; ☁️博客首页&#xff1a;CSDN主页听风与他 &#x1f304;每日一句&#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维格表作为新一代数据生产力平台&#xff0c…...

配电房综合监控系统

配电房综合监控系统是一种集成了实时监控、数据采集、远程控制等多功能的系统&#xff0c;用于对配电房进行全方位的监测和管理。 力安科技配电室综合监控系统依托电易云-智慧电力物联网&#xff0c;实现配电室环境监测、有害气体监测、安防监控、采暖通风、门禁、灯光、风机、…...

【JavaSE】集合(学习笔记)

一、数据结构 1、栈 压栈 / 弹栈栈顶元素、栈底元素先进后出 2、队列 入队列 / 出队列前端、后端先进先出 3、数组 查询效率高&#xff0c;增删效率低 4、链表 查询效率低(必须从头找)&#xff0c;增删效率高 5、哈希表 比较方法哈希值equals结构&#xff1a;数组 链…...

Mybatis 的简单运用介绍

Mybatis 用于操作数据库 操作数据库肯定需要: 1.SQL语句 2.数据库对象和 java 对象的映射 接下来我们看看怎么使用 Mybatis 我们先搞一些数据库内容 然后将其这些内容和Java对象进行映射 再创建一个类实现 select * from 再写一个类证明上述代码是否可以实现 别忘了在appli…...

python的itertools库

itertools常用的方法如下&#xff1a; import itertools 1. 生成的列表累加&#xff0c;在生成新的列表x itertools.accumulate(range(10))print(list(x))结果&#xff1a;[0, 1, 3, 6, 10, 15, 21, 28, 36, 45] 2. 连接多个列表或者迭代器x itertools.chain(range(3), rang…...

STM32/GD32_分散加载

Q&#xff1a;如何将一个变量、某个源文件的函数在编译阶段就存储在用户指定的区域&#xff1f; KEIL环境&#xff1a;.map后缀文件、.sct后缀文件 IAR环境&#xff1a;.map后缀文件、.icf后缀文件 【map文件】 对固件里面的变量、函数、常量等元素的存储空间进行分配的说明…...

go clean

移除目标文件和缓存文件。 更多信息&#xff1a;https://golang.org/cmd/go/#hdr-Remove_object_files_and_cached_files. 只打印移除命令&#xff0c;而不会真正移除任何东西&#xff1a; go clean -n 删除编译缓存&#xff1a; go clean -cache 删除所有测试结果缓存&…...

BUUCTF [ACTF新生赛2020]swp 1

BUUCTF:https://buuoj.cn/challenges 题目描述&#xff1a; 得到的 flag 请包上 flag{} 提交。 密文&#xff1a; 下载附件&#xff0c;得到一个.tar文件。 解题思路&#xff1a; 1、使用WinRAR解压.tar文件&#xff0c;得到两个.zip文件。 解压wget.zip文件&#xff0c;得…...

【PTA题目】7-4 缩写期刊名 分数 10

7-4 缩写期刊名 分数 10 全屏浏览题目 切换布局 作者 黄龙军 单位 绍兴文理学院 科研工作者经常要向不同的期刊投稿。但不同期刊的参考文献的格式往往各不相同。有些期刊要求参考文献所发表的期刊名必须采用缩写形式&#xff0c;否则直接拒稿。现对于给定的期刊名&#xff…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...