大小堆运用巧解数据流的中位数

一、思路
我们将所有数据平分成两份,前面那一部分用小堆来存,后面的部分用大堆来存,这样我们就能立刻拿到中间位置的值。
如果是奇数个数字,那么我们就将把中间值放在前面的大堆里,所以会有两种情况,我们将大堆成为left,小堆成为right。
- 当数据量是偶数的时候,left.size() == right.size(),这时候中间值就是left.top()
- 当数据量是奇数的时候,这时候的left.size() == right.size() + 1,这时候的中位数就是 (left.size() + right.size()) / 2.0
二、如何存储数据?
因为左边是大堆,右边是小堆,这时候会有两个大类的情况
第一种 left.size() = right.size()
这时候,由于左边的数据都是会比left.top()小,右边的数据都会比左边的数据大,所以我们可以根据这个条件开进行讨论
假如要插入的数据是num
- 如果left.empty() || num <= left.top() ,这时候就直接将num插进左边的大堆中
- 如果num > left.top(),这时候应该要插进右边的小堆,但由于我们规定只能两边数据相等,或者右边的比左边的数据量多一个,所以这时候我们要:
1.先把数据插入进right,
2.然后拿到right.top(),因为这是right的最小值
3.将right.top() 插进 left.top()中,然后再让right.pop()
第二种 left.size() > right.size()
- 如果num > left.top() ,直接把num插进right中
- 如果num <= left.top(), 这时候由于left的大小比right多1,所以我们可以参考第一种情况那样
- 把数据插进left
- 将left.top() 插入到 right中
- left.pop()
三、代码
class MedianFinder {
public:priority_queue<int> left;priority_queue<int, vector<int>, greater<int>> right;MedianFinder() {}void addNum(int num) {if(left.size() == right.size()){if(left.empty() || left.top() >= num) {left.push(num);}else if(left.top() < num) {right.push(num);int y = right.top();right.pop();left.push(y);}}else{if(left.top() >= num) {left.push(num);right.push(left.top());left.pop();}else {right.push(num);}}}double findMedian() {if(left.size() == right.size()) return (left.top() + right.top()) / 2.0;else return left.top();}
};
相关文章:
大小堆运用巧解数据流的中位数
一、思路 我们将所有数据平分成两份,前面那一部分用小堆来存,后面的部分用大堆来存,这样我们就能立刻拿到中间位置的值。 如果是奇数个数字,那么我们就将把中间值放在前面的大堆里,所以会有两种…...
AI能力边界不断扩展,将对国家安全产生深远影响
文 | 中国信息安全测评中心 王欣 随着 ChatGPT 的发布及相关应用的落地,人工智能技术给全球各个行业带来了一波又一波冲击。GPT-4 多模态大型语言模型更是将人工智能的能力提升到新的高度,无论从技术先进性还是应用实践能力来看,此模型均可被…...
【UnityShader入门精要学习笔记】第十六章 Unity中的渲染优化技术 (上)
本系列为作者学习UnityShader入门精要而作的笔记,内容将包括: 书本中句子照抄 个人批注项目源码一堆新手会犯的错误潜在的太监断更,有始无终 我的GitHub仓库 总之适用于同样开始学习Shader的同学们进行有取舍的参考。 文章目录 移动平台上…...
GPT-4o:免费且更快的模型
OpenAI GPT-4o 公告 OpenAI 推出了增强版 GPT-4 模型——OpenAI GPT-4o,用于支持 ChatGPT。首席技术官 Mira Murati 表示,更新后的模型速度更快,并在文本、视觉和音频处理方面有了显著提升。GPT-4o 将免费向所有用户开放,付费用户…...
docker部署fastdfs
我的镜像包地址 链接:https://pan.baidu.com/s/1j5E5O1xdyQVfJhsOevXvYg?pwdhcav 提取码:hcav docker load -i gofast.tar.gz拉取gofast docker pull sjqzhang/go-fastdfs启动gofast docker run -d --name fastdfs -p 8080:8080 -v /opt/lijia/lijia…...
【劲舞团game】
编写《劲舞团》这样的游戏代码是一个复杂的过程,涉及到游戏引擎的使用、图形渲染、物理模拟、音频处理、网络通信等多个方面。以下是一个非常简化的步骤,用于说明如何开始编写一个基于Unity引擎的简单舞蹈游戏: 1. 准备开发环境 下载并安装…...
Day15—图像爬虫与简单处理
图像爬虫是一种专门用于从互联网上下载图像的网络爬虫。除了文本内容,图像也是网站中的重要组成部分,它们可以用于多种目的,如图像识别、内容分析、数据备份等。 环境准备 首先,确保你的环境中已安装Python和必要的库。如果没有安装Pillow库,可以通过以下命令安装:pip in…...
Rust基础学习-Rust中的文件操作
文件结构 在Rust中,std::fs::File 结构体代表一个文件。它允许我们对文件执行读/写操作。文件 I/O 是通过提供与文件系统交互的功能的 std::fs 模块执行的。 File 结构体中的所有方法都返回std::io::Result的变体,或者简单地是 Result 枚举。这里会涉及…...
Activator.CreateInstance 与 Type.InvokeMember的区别
文章目录 一、使用 Activator.CreateInstance 创建实例1、使用 Activator.CreateInstance 的优点和缺点2、使用 Activator.CreateInstance 的代码示例 二、使用 Type.InvokeMember 创建实例1、使用 Type.InvokeMember 的优点和缺点2、使用 Type.InvokeMember 的代码示例 三、Ac…...
Java18+App端采用uniapp+开发工具 idea hbuilder智能上门家政系统源码,一站式家政服务平台开发家政服务
Java18App端采用uniapp开发工具 idea hbuilder智能上门家政系统源码,一站式家政服务平台开发 家政服务 家政服务是一个专为家政服务人员设计的平台,该平台旨在提供便捷、高效的工作机会,同时确保服务质量和客户体验。 以下是关于家政服务师…...
【MySQL】探索 MySQL 的 GROUP_CONCAT 函数
缘分让我们相遇乱世以外 命运却要我们危难中相爱 也许未来遥远在光年之外 我愿守候未知里为你等待 我没想到为了你我能疯狂到 山崩海啸没有你根本不想逃 我的大脑为了你已经疯狂到 脉搏心跳没有你根本不重要 🎵 邓紫棋《光年之外》 什么是 GRO…...
SpringBoot整合RabbitMQ (持续更新中)
RabbitMQ 官网地址:RabbitMQ: One broker to queue them all | RabbitMQ RabbitMQ 与 Erlang 版本兼容关系 3.13.0 26.0 26.2.x The 3.13 release series is compatible with Erlang 26. OpenSSL 3 support in Erlang is considered to be mature and ready for…...
瑞鑫RK3588 画中画 OSD 效果展示
这些功能本来在1126平台都实现过 但是迁移到3588平台之后 发现 API接口变化较大 主要开始的时候会比较费时间 需要找到变动接口对应的新接口 之后 就比较好操作了 经过几天的操作 已实现 效果如下...
【全开源】防伪溯源一体化管理系统源码(FastAdmin+ThinkPHP+Uniapp)
🔍防伪溯源一体化管理系统:守护品质,追溯无忧 一款基于FastAdminThinkPHP和Uniapp进行开发的多平台(微信小程序、H5网页)溯源、防伪、管理一体化独立系统,拥有强大的防伪码和溯源码双码生成功能࿰…...
自然语言处理:第三十三章FILCO:过滤内容的RAG
文章链接: [2311.08377] Learning to Filter Context for Retrieval-Augmented Generation (arxiv.org) 项目地址: zorazrw/filco: [Preprint] Learning to Filter Context for Retrieval-Augmented Generaton (github.com) 在人工智能领域,尤其是在开放域问答和事…...
js:flex弹性布局
目录 代码: 1、 flex-direction 2、flex-wrap 3、justify-content 4、align-items 5、align-content 代码: <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewp…...
Pytorch常用函数用法归纳:创建tensor张量
1.torch.arange() (1)函数原型 torch.arange(start,end,step,*,out,dtype,layout,device,requires_grad) (2)参数说明: 参数名称参数类型参数说明startNumber起始值,默认值为0endNumber结束值,取不到,为开区间stepNumber步长值࿰…...
WPF前端:一个纯Xaml的水平导航栏
效果图: 代码: 1、样式代码,可以写在窗体资源处或者样式资源文件中 <Style x:Key"MenuRadioButtonStyle" TargetType"{x:Type RadioButton}"><Setter Property"FontSize" Value"16" />…...
谷粒商城实战(033 业务-秒杀功能4-高并发问题解决方案sentinel 1)
Java项目《谷粒商城》架构师级Java项目实战,对标阿里P6-P7,全网最强 总时长 104:45:00 共408P 此文章包含第326p-第p331的内容 关注的问题 sentinel(哨兵) sentinel来实现熔断、降级、限流等操作 腾讯开源的tendis,…...
STM32项目分享:智能家居(机智云)系统
目录 一、前言 二、项目简介 1.功能详解 2.主要器件 三、原理图设计 四、PCB硬件设计 1.PCB图 2.PCB板及元器件图 五、程序设计 六、实验效果 七、资料内容 项目分享 一、前言 项目成品图片: 哔哩哔哩视频链接: https://www.bilibili.c…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
