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

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...

flow_controllers

关键点&#xff1a; 流控制器类型&#xff1a; 同步&#xff08;Sync&#xff09;&#xff1a;发布操作会阻塞&#xff0c;直到数据被确认发送。异步&#xff08;Async&#xff09;&#xff1a;发布操作非阻塞&#xff0c;数据发送由后台线程处理。纯同步&#xff08;PureSync…...

Yii2项目自动向GitLab上报Bug

Yii2 项目自动上报Bug 原理 yii2在程序报错时, 会执行指定action, 通过重写ErrorAction, 实现Bug自动提交至GitLab的issue 步骤 配置SiteController中的actions方法 public function actions(){return [error > [class > app\helpers\web\ErrorAction,],];}重写Error…...

【Java】Ajax 技术详解

文章目录 1. Filter 过滤器1.1 Filter 概述1.2 Filter 快速入门开发步骤:1.3 Filter 执行流程1.4 Filter 拦截路径配置1.5 过滤器链2. Listener 监听器2.1 Listener 概述2.2 ServletContextListener3. Ajax 技术3.1 Ajax 概述3.2 Ajax 快速入门服务端实现:客户端实现:4. Axi…...

__VUE_PROD_HYDRATION_MISMATCH_DETAILS__ is not explicitly defined.

这个警告表明您在使用Vue的esm-bundler构建版本时&#xff0c;未明确定义编译时特性标志。以下是详细解释和解决方案&#xff1a; ‌问题原因‌&#xff1a; 该标志是Vue 3.4引入的编译时特性标志&#xff0c;用于控制生产环境下SSR水合不匹配错误的详细报告1使用esm-bundler…...

Q1起重机指挥理论备考要点分析

Q1起重机指挥理论备考要点分析 一、考试重点内容概述 Q1起重机指挥理论考试主要包含三大核心模块&#xff1a;安全技术知识&#xff08;占40%&#xff09;、指挥信号规范&#xff08;占30%&#xff09;和法规标准&#xff08;占30%&#xff09;。考试采用百分制&#xff0c;8…...