当前位置: 首页 > 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…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...