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

算法通关村第十四关:黄金挑战-数据流的中位数

黄金挑战-数据流的中位数

1.数据流中中位数的问题

LeetCode295
https://leetcode.cn/problems/find-median-from-data-stream/

思路分析

中位数的问题,我们一般都可以用 大顶堆+小顶堆 来求解

小顶堆(minHeap):存储所有元素中较大的一半,堆顶元素是其中最小的数
大顶堆(maxHeap):存储所有元素中较小的一半,堆顶元素是其中最大的数

相当于,把所有元素分成了大和小两半,计算中位数,只需要大的那半的最小值和小的那半的最大值即可。

如[1,2,3,4,5],分成小顶堆[3,4,5],大顶堆[2,1],中位数为3

过程
加1 小顶堆[1] 大顶堆[] 中位数 1
加2 小顶堆[2] 大顶堆[1] 中位数 (2+1)/2
加3 小顶堆[2,3] 大顶堆[1] 中位数 3
加4 小顶堆[3,4] 大顶堆[2,1] 中位数 (3+2)/2
加5 小顶堆[3,4,5] 大顶堆[2,1] 中位数 3

代码实现

Java中的堆(即优先队列)可方便实现,c++、python里没有提供堆结构,需要自己构造

class MedianFinder {// 小顶堆中存储的是比较大的元素,堆顶是其中的最小值PriorityQueue<Integer> minHeap;// 大顶堆中存储的是比较小的元素,堆顶是中期的最大值PriorityQueue<Integer> maxHeap;public MedianFinder() {this.minHeap = new PriorityQueue<>();this.maxHeap = new PriorityQueue<>((a, b) -> b - a);}public void addNum(int num) {// 小顶堆存储的是比较大的元素,num大于小顶堆中根元素时进入minHeapif (minHeap.isEmpty() || num > minHeap.peek()){minHeap.offer(num);// 如果minHeap比maxHeap多2个元素,就平衡一下if (minHeap.size() - maxHeap.size() > 1){maxHeap.offer(minHeap.poll());}}else{maxHeap.offer(num);// 这样可以保证多的那个元素肯定在minHeapif(maxHeap.size() - minHeap.size() > 0){minHeap.offer(maxHeap.poll());}}}public double findMedian() {if(minHeap.size() > maxHeap.size()){return minHeap.peek();}else if(minHeap.size() < maxHeap.size()){return maxHeap.peek();}else{return (minHeap.peek() + maxHeap.peek())/2.0;}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

相关文章:

算法通关村第十四关:黄金挑战-数据流的中位数

黄金挑战-数据流的中位数 1.数据流中中位数的问题 LeetCode295 https://leetcode.cn/problems/find-median-from-data-stream/ 思路分析 中位数的问题&#xff0c;我们一般都可以用 大顶堆小顶堆 来求解 小顶堆&#xff08;minHeap&#xff09;&#xff1a;存储所有元素中…...

【2023集创赛】国家集创中心杯三等奖:不对称轻失配运算放大器

本文为2023年第七届全国大学生集成电路创新创业大赛&#xff08;“集创赛”&#xff09;国家集创中心杯三等奖作品分享&#xff0c;参加极术社区的【有奖征集】分享你的2023集创赛作品&#xff0c;秀出作品风采&#xff0c;分享2023集创赛作品扩大影响力&#xff0c;更有丰富电…...

手写Mybatis:第18章-一级缓存

文章目录 一、目标&#xff1a;一级缓存二、设计&#xff1a;一级缓存三、实现&#xff1a;一级缓存3.1 工程结构3.2 一级缓存类图3.3 一级缓存实现3.3.1 定义缓存接口3.3.2 实现缓存接口3.3.3 创建缓存KEY3.3.4 NULL值缓存key 3.4 定义缓存机制、占位符和修改配置文件3.4.1 定…...

哈夫曼编码实现文件的压缩和解压

程序示例精选 哈夫曼编码实现文件的压缩和解压 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对《哈夫曼编码实现文件的压缩和解压》编写代码&#xff0c;代码整洁&#xff0c;规则&#xff0…...

解决六大痛点促进企业更好使用生成式AI,亚马逊云科技顾凡采访分享可用方案

亚马逊云科技大中华区战略业务发展部总经理顾凡在接受21世纪经济报道记者专访时表示&#xff0c;生成式人工智能将从四个方面为企业带来机遇&#xff1a;第一是创造全新的客户体验&#xff1b;第二是提高企业内部员工的生产力&#xff1b;第三是帮助企业提升业务运营效率&#…...

Qt 定时器放在线程中执行,支持随时开始和停止定时器。

前言&#xff1a;因为项目需要定时检查网络中设备是否能连通&#xff0c;需要定时去做ping操作&#xff0c;若是网络不通&#xff0c;则ping花费时间比较久&#xff08;局域网大概4秒钟才能结束&#xff0c;当然如果设置超时时间啥的&#xff0c;也能很快返回&#xff0c;就是会…...

java 过滤器 接口(API)验证入参,验签(sign) Demo

java 过滤器 接口&#xff08;API&#xff09;验证入参&#xff0c;验签&#xff08;sign&#xff09; Demo 一、思路 1、配置yml文件; 2、创建加载配置文件类; 3、继承 OncePerRequestFilter 重写方法 doFilterInternal; 4、注册自定义过滤器; 二、步骤 1、配置yml文件; ###系…...

独家!微信正在灰测一款全新消金产品

来源 | 镭射财经&#xff08;leishecaijing&#xff09; 「镭射财经」独家获悉&#xff0c;微信将推出一款名为“微信分期”的新消费信贷产品&#xff0c;目前该产品正处于小范围灰测阶段&#xff0c;还未正式上线。上线后&#xff0c;微信将运营微信分付和微信分期两款自营消…...

阿秀C++笔记-学习记录

81.C中的组合和继承相比的优缺点 在C中组合一对象系用描述对象包对象系组一个拥对象例其变合类的含的现。这的量类当有员被创建。 以下一个示例&#xff0c;展示了在C中如何实现组合关系&#xff1a; class Engine {// Engine class definition... };class Car {Engine engi…...

前端入门到入土?

文章目录 前言http和https的区别&#xff0c;https加密的原理是&#xff1f;区别https的加密原理 TCP为什么要三次握手&#xff1f;proxy代理的原理&#xff1f;内存泄漏&#xff1f;什么是内存泄漏&#xff1f;为什么会有内存泄漏&#xff1f;内存泄漏的情况&#xff1f;如何防…...

架构设计基础设施保障IaaS之网络

目录 1 DNS运用1.1 DNS功能作用1.2 DNS配置实践 2 DNS生产最佳实践方案2.1 全球加速功能2.2 不同运营商的加速方案2.3 全球业务高可用方案2.4 跨地域负载均衡 3 DNS域名劫持解决方案4 CDN剖析4.1 CDN原理4.2 缓存过期配置处理流程4.3 缓存配置规则 5 CDN运用6 CDN最佳实践方案6…...

zabbix安装部署

前期准备&#xff1a;安装mysql数据库和nginx 一、下载zabbix rpm -Uvh https://repo.zabbix.com/zabbix/4.4/rhel/7/x86_64/zabbix-release-4.4-1.el7.noarch.rpm yum-config-manager --enable rhel-7-server-optional-rpms yum install epel-release numactl yum install…...

零碎的C++

构造函数和析构函数 构造函数不能是虚函数&#xff0c;而析构函数可以是虚函数。原因如下&#xff1a; 构造函数不能是虚函数&#xff0c;因为在执行构造函数时&#xff0c;对象还没有完全创建&#xff0c;还没有分配内存空间&#xff0c;也没有初始化虚函数表指针。如果构造…...

模糊测试面面观 | 模糊测试是如何发现异常情况的?

协议模糊测试是一种用于评估通信协议、文件格式和API实现系统安全性和稳定性的关键技术。在模糊测试过程中&#xff0c;监视器扮演着关键角色&#xff0c;它们能够捕获异常情况、错误响应、资源利用等&#xff0c;为测试人员提供有价值的信息&#xff0c;有助于发现潜在漏洞和问…...

C#备份数据库文件

c#备份数据库文件完整代码 sqlServer 存储过程&#xff1a; USE [PSIDBase] GO /****** Object: StoredProcedure [dbo].[sp_BackupDB] Script Date: 2023/8/31 16:49:02 ******/ SET ANSI_NULLS ON GO SET QUOTED_IDENTIFIER ON GOALTER procedure [dbo].[sp_BackupDB]…...

行军遇到各种复杂地形怎么处理?

行军遇到各种复杂地形怎么处理&#xff1f; 【安志强趣讲《孙子兵法》第30讲】 【原文】 凡军好高而恶下&#xff0c;贵阳而贱阴&#xff0c;养生而处实&#xff0c;军无百疾&#xff0c;是谓必胜。 【注释】 阳&#xff0c;太阳能照到的地方。阴&#xff0c;太阳照不到的地方。…...

Python Number(数字).............................................

Python Number 数据类型用于存储数值。 数据类型是不允许改变的,这就意味着如果改变 Number 数据类型的值&#xff0c;将重新分配内存空间。 以下实例在变量赋值时 Number 对象将被创建&#xff1a; var1 1 var2 10您也可以使用del语句删除一些 Number 对象引用。 del语句…...

设置 Hue Server 与 Hue Web 界面之间的会话超时时间

设置 Hue Server 与 Hue Web 界面之间的会话超时时间 在 CDH 的 Hue 中&#xff0c;Auto Logout Timeout 参数表示用户在不活动一段时间后将自动注销&#xff08;登出&#xff09;的超时时间。当用户在 Hue 中处于不活动状态超过该设定时间时&#xff0c;系统将自动注销用户&am…...

openGauss学习笔记-57 openGauss 高级特性-并行查询

文章目录 openGauss学习笔记-57 openGauss 高级特性-并行查询57.1 适用场景与限制57.2 资源对SMP性能的影响57.3 其他因素对SMP性能的影响57.4 配置步骤 openGauss学习笔记-57 openGauss 高级特性-并行查询 openGauss的SMP并行技术是一种利用计算机多核CPU架构来实现多线程并行…...

软考(1)-面向对象的概念

目录 一. 软考基本信息 1. 软考时间&#xff1a; 2. 软考科目&#xff1a; 3.专业知识介绍 -- 综合知识考点分布 4. 专业介绍 -- 软件设计考点分布 二. 面向对象概念 1. 封装 考点一&#xff1a;对象 考点二&#xff1a;封装private 2. 继承 考点三&#xff1a;类 考…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...