力扣295. 数据流的中位数

Problem: 295. 数据流的中位数

文章目录

  • 题目描述
  • 思路
  • 复杂度
  • Code

题目描述

在这里插入图片描述在这里插入图片描述

思路

1.定义一个大顶堆和小顶堆;
2.当添加的数据小于大顶堆的堆顶元素或者大顶堆为空时,将元素添加到大顶堆;当元素大于大顶堆堆顶元素时添加到小顶堆;同时维护大小顶堆,当大顶堆的元素个数小于小顶堆时,将小顶堆多出大顶堆个数的堆顶元素拿出添加到大顶堆;当小顶堆元素小于大顶堆元素个数减1时将大顶堆多出的堆顶元素添加到小顶堆;
3.当大小顶堆的元素个数一样时,取各自的堆顶元素相加除以2;否则取出大顶堆的堆顶元素;

复杂度

时间复杂度:

O ( l o g n ) O(logn) O(logn);其中 n n n为数据数据流的数据个数

空间复杂度:

O ( n ) O(n) O(n)

Code

class MedianFinder {/* Maintain a large top heap and a small top heap */private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});private PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}});public MedianFinder() {}/*** Data flow inserts data** @param num Data to be inserted*/public void addNum(int num) {if (maxHeap.isEmpty() || num <= maxHeap.peek()) {maxHeap.add(num);} else {minHeap.add(num);}/**Maintain the number relationship between two heaps1. The number of elements in the large top heap is not less than that in the small top heap2. The number of small top heap elements can be less than the number of large top heap elements minus 1*/while (maxHeap.size() < minHeap.size()) {Integer temp = minHeap.poll();maxHeap.add(temp);}while (minHeap.size() < maxHeap.size() - 1) {Integer temp = maxHeap.poll();minHeap.add(temp);}}/*** Find the median** @return double*/public double findMedian() {if (maxHeap.size() == minHeap.size()) {return (minHeap.peek() + maxHeap.peek()) / 2f;} else {return maxHeap.peek();}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/320389.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

18 如何设计微服务才能防止宕机?

在上一讲里&#xff0c;介绍了构建一个稳健的微服务的具体法则&#xff1a;防备上游、做好自己、怀疑下游&#xff0c; 并介绍了为什么要防备上游&#xff0c;以及一些防备上游的具体手段。 在本讲里&#xff0c;咱们一起来学习&#xff0c;做好微服务自身的设计和代码编写的常…

Android4.4真机移植过程笔记(一)

1、RK源码编译 获取内核源码&#xff1a; git clone git172.28.1.172:rk3188_kernel -b xtc_ok1000 内核编译环境&#xff1a; 从172.28.1.132编译服务器的/data1/ZouZhiPing目录下拷贝toolchain.tar.gz&#xff08;交叉编译工具链&#xff09;并解压到与rk3188_kernel同级目…

【项目部署】手把手带你从零部署项目:宝塔 + uwsgi + Django + 腾讯云 + Websocket

1. 前言 哈喽&#xff0c;大家好&#xff0c;我是jiaoxingk。今天带来的是有关Django项目部署的教程。 当我们完成了一个项目作品之后&#xff0c;我们肯定会迫不及待的就准备上线部署啦&#xff0c; 这篇教程将带你从服务器的配置选购&#xff0c;再通过安装宝塔的形式进行项目…

QT程序通过GPIB-USB-HS转接线控制数字万用表

1、硬件准备 1.1、数字万用表 型号 &#xff1a;Agilent 34401A 前面图示&#xff1a; 后面图示&#xff1a;有GPIB接口 1.2、GPIB-USB-HS转接线 2、GPIB协议基础了解 2.1、引脚 8条数据线&#xff1a;DIO1 ~ DIO8 5条管理线&#xff1a;IFC、ATN、REN、EOI、SRQ 3条交握线…

拆单算法交易(Algorithmic Trading)

TWAP TWAP交易时间加权平均价格Time Weighted Average Price 模型&#xff0c;是把一个母单的数量平均地分配到一个交易时段上。该模型将交易时间进行均匀分割&#xff0c;并在每个分割节点上将拆分的订单进行提交。例如&#xff0c;可以将某个交易日的交易时间平均分为N 段&am…

【云原生】Pod 的生命周期(一)

【云原生】Pod 的生命周期&#xff08;一&#xff09;【云原生】Pod 的生命周期&#xff08;二&#xff09; Pod 的生命周期&#xff08;一&#xff09; 1.Pod 生命期2.Pod 阶段3.容器状态3.1 Waiting &#xff08;等待&#xff09;3.2 Running&#xff08;运行中&#xff09;3…

鸿蒙内核源码分析(消息队列篇) | 进程间如何异步传递大数据

基本概念 队列又称消息队列&#xff0c;是一种常用于任务间通信的数据结构。队列接收来自任务或中断的不固定长度消息&#xff0c;并根据不同的接口确定传递的消息是否存放在队列空间中。 任务能够从队列里面读取消息&#xff0c;当队列中的消息为空时&#xff0c;挂起读取任务…

Discourse 清理存储空间的方法

Discourse 使用一段时间以后会发现硬盘空间占用非常多。 主要是因为 Docker Image 的问题&#xff0c;如果升级次数越多&#xff0c;空间占用越多。 运行下面的命令&#xff1a; ./launcher cleanup 能够帮助你清理 Discourse 占用的空间。 如下面代码所示&#xff1a; […

牛客热题:单链表排序

&#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;力扣刷题日记 &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 文章目录 牛客热题&#xff1a;单链表排序题目链接方法一&…

Windows php 安装 Memcached扩展、php缺失 Memcached扩展、Class ‘Memcached‘ not found

在Windows系统下如何安装 php Memcached 扩展 下载dll文件 pecl地址&#xff1a;https://pecl.php.net/package/memcached 根据版本进行选择 &#xff1a; 解压下载的文件后得到了这么样的文件结构&#xff1a; 配置 移动dll文件到相应文件位置 重点&#xff1a; libme…

jdk环境安装

jdk安装 创建软件安装的目录 mkdir -p /bigdata/{soft,server} /bigdata/soft 安装文件的存放目录 /bigdata/server 软件安装的目录 把安装的软件上传到/bigdata/soft 目录 解压到指定目录 -C :指定解压到指定目录 tar -zxvf /bigdata/soft/jdk-8u241-linux-x64.tar.gz -C /b…

【Osek网络管理测试】[TG3_TC3]tSleepRequestMin_L

&#x1f64b;‍♂️ 【Osek网络管理测试】系列&#x1f481;‍♂️点击跳转 文章目录 1.环境搭建2.测试目的3.测试步骤4.预期结果5.测试结果 1.环境搭建 硬件&#xff1a;VN1630 软件&#xff1a;CANoe 2.测试目的 验证DUT进入NMLimpHome状态后请求睡眠的最短时间是否正确…

Android --- 消息机制与异步任务

在Android中&#xff0c;只有在UIThread(主线程)中才能直接更新界面&#xff0c; 在Android中&#xff0c;长时间的工作联网都需要在workThread(分线程)中执行 在分线程中获取服务器数据后&#xff0c;需要立即到主线程中去更新UI来显示数据&#xff0c; 所以&#xff0c;如…

NI CRIO 9045 LABVIEW2020

1.labview工程如果要访问CRIO&#xff0c;需要设置以下&#xff0c;否则在项目中连接失败。 2.项目中如果要传文件&#xff0c;需要安装WebDEV 3.使用WebDAV将文件传输到实时(RT)目标 https://knowledge.ni.com/KnowledgeArticleDetails?idkA03q000000YGytCAG&lzh-CN

Mars3d实现用一个button控制一个map.control的显示与隐藏

原生js,想做一个button,控制比如compass的显示与隐藏 点一下显示 再次单击的时候就隐藏掉 写了一个function控制显示隐藏 function addCompass(){ if(compass.showtrue) { compass.showfalse; } else{ compass.showtrue; } } 功能示例(Vue版) | Mars3D三维可视化平台 | 火星…

深入了解C/C++的内存区域划分

&#x1f525;个人主页&#xff1a;北辰水墨 &#x1f525;专栏&#xff1a;C学习仓 本节我们来讲解C/C的内存区域划分&#xff0c;文末会附加一道题目来检验成果&#xff08;有参考答案&#xff09; 一、大体有哪些区域&#xff1f;分别存放什么变量开辟的空间&#xff1f; …

【微服务】网关(详细知识以及登录验证)

微服务网关 网关网关路由快速入门路由属性 路由断言网关登录校验自定义过滤器实现登录校验网关传递用户OpenFeign传递用户 网关 网络的关口&#xff0c;负责请求的路由&#xff0c;转发&#xff0c;身份校验 当我们把一个单体项目分成多个微服务并部署在多台服务器中&#xff…

Redis__数据类型

文章目录 &#x1f60a; 作者&#xff1a;Lion J &#x1f496; 主页&#xff1a; https://blog.csdn.net/weixin_69252724 &#x1f389; 主题&#xff1a;Redis__数据类型 ⏱️ 创作时间&#xff1a;2024年04月28日 ———————————————— 这里写目录标题 文…

大模型争霸的下一站:不仅是超越GPT-4,更是寻求模型之间的平衡应用

文 | 智能相对论 作者 | 沈浪 知名科学杂志《Nature》发表了一篇关于大模型规模参数大小争议的文章《In Al, is bigger always better?》——AI大模型&#xff0c;越大越好吗&#xff1f;随着大模型应用走向实践&#xff0c;这一问题不可避免地成为了当前AI行业发展的焦点与…

迅雷永久破解

链接&#xff1a;https://pan.baidu.com/s/1ZGb1ljTPPG3NFsI8ghhWbA?pwdok7s 下载后解压 以管理员身份运行绿化.bat&#xff0c;会自动生成快捷方式&#xff0c;如果没有可以在program中运行Thunder.exe