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

力扣 295. 数据流的中位数

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

题目

  • 数据流中不断有数添加进来,add 表示添加数据,find 返回数据流中的中位数

思路

  • 大根堆存储数据流中偏小的数据
  • 小根堆存储数据流中偏大的数据
  • 若当前的 num 比大根堆的 top 小,则加入到大根堆,反义加入小根堆
  • 保证大根堆和小根堆的 size 相差小于等于 1,超过时,挪动一下数据
  • 中位数则是 size 大的那个堆的 top,若相等则取 top / 2

代码

class MedianFinder {
public:MedianFinder() {size = 0;}void addNum(int num) {size++;if (maxheap.empty()) {maxheap.push(num);return;}if (num <= maxheap.top()) {maxheap.push(num);} else {minheap.push(num);}if (maxheap.size() - minheap.size() == 2) {minheap.push(maxheap.top());maxheap.pop();}if (minheap.size() - maxheap.size() == 2) {maxheap.push(minheap.top());minheap.pop();}}double findMedian() {if (maxheap.size() > minheap.size()) {return maxheap.top();}if (minheap.size() > maxheap.size()) {return minheap.top();} return ((double)maxheap.top() + minheap.top()) / 2;}std::priority_queue<int, std::vector<int>> maxheap;std::priority_queue<int, std::vector<int>, std::greater<int>> minheap;int size;};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

相关文章:

力扣 295. 数据流的中位数

&#x1f517; https://leetcode.cn/problems/find-median-from-data-stream/ 题目 数据流中不断有数添加进来&#xff0c;add 表示添加数据&#xff0c;find 返回数据流中的中位数 思路 大根堆存储数据流中偏小的数据小根堆存储数据流中偏大的数据若当前的 num 比大根堆的…...

【Linux】进程状态和优先级

个人主页~ 进程状态和优先级 一、进程状态1、操作系统进程状态&#xff08;一&#xff09;运行态&#xff08;二&#xff09;阻塞态&#xff08;三&#xff09;挂起态 2、Linux进程状态&#xff08;一&#xff09;R-运行状态并发执行 &#xff08;二&#xff09;S-浅度睡眠状态…...

携程Java开发面试题及参考答案 (200道-上)

说说四层模型、七层模型。 七层模型(OSI 参考模型) 七层模型,即 OSI(Open System Interconnection)参考模型,是一种概念模型,用于描述网络通信的架构。它将计算机网络从下到上分为七层,各层的功能和作用如下: 物理层:物理层是计算机网络的最底层,主要负责传输比特流…...

Docker 部署教程jenkins

Docker 部署 jenkins 教程 Jenkins 官方网站 Jenkins 是一个开源的自动化服务器&#xff0c;主要用于持续集成&#xff08;CI&#xff09;和持续交付&#xff08;CD&#xff09;过程。它帮助开发人员自动化构建、测试和部署应用程序&#xff0c;显著提高软件开发的效率和质量…...

深入理解开放寻址法中的三种探测序列

一、引言 开放寻址法是解决散列表中冲突的一种重要方法&#xff0c;当发生冲突&#xff08;即两个不同的键通过散列函数计算得到相同的散列值&#xff09;时&#xff0c;它会在散列表中寻找下一个可用的存储位置。而探测序列就是用于确定在发生冲突后&#xff0c;依次尝试哪些…...

图像噪声处理技术:让图像更清晰的艺术

在这个数字化时代&#xff0c;图像作为信息传递的重要载体&#xff0c;其质量直接影响着我们的视觉体验和信息解读。然而&#xff0c;在图像采集、传输或处理过程中&#xff0c;难免会遇到各种噪声干扰&#xff0c;如高斯噪声、椒盐噪声等&#xff0c;这些噪声会降低图像的清晰…...

linux运行级别

运行级别&#xff1a;指linux系统在启动和运行过程中所处的不同的状态。 运行级别之间的切换&#xff1a;init (级别数) 示例&#xff1a; linux的运行级别一共有7种&#xff0c;分别是&#xff1a; 运行级别0&#xff1a;停机状态 运行级别1&#xff1a;单用户模式/救援模式…...

深入剖析Electron的原理

Electron是一个强大的跨平台桌面应用开发框架&#xff0c;它允许开发者使用HTML、CSS和JavaScript来构建各种桌面应用程序。了解Electron的原理对于开发者至关重要&#xff0c;这样在设计应用时能更合理&#xff0c;遇到问题也能更准确地分析和解决。下面将从多个方面深入剖析E…...

C++ 游戏开发:完整指南

目录 什么是游戏开发&#xff1f; 为什么选择 C 进行游戏开发&#xff1f; C 游戏开发&#xff1a;完整指南 1. 理解游戏开发的基础 2. 学习游戏引擎 3. 精通 C 进行游戏开发 4. 学习数学在游戏开发中的应用 5. 探索图形编程 6. 专注于游戏开发的某一领域 7. 通过游戏项目进行实…...

WebForms SortedList 深度解析

WebForms SortedList 深度解析 引言 在Web开发领域,对于数据结构的理解与应用至关重要。其中,SortedList类在WebForms中是一个常用的数据结构,它能够帮助开发者高效地管理有序数据集合。本文将深入解析SortedList类在WebForms中的应用,包括其基本概念、常用方法、性能特点…...

【hot100】刷题记录(12)-回文链表

题目描述&#xff1a; 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为 回文链表 。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true示例 2&#xff1a; …...

深入理解 Unix Shell 管道 Pipes:基础和高级用法 xargs tee awk sed等(中英双语)

深入理解 Unix Shell 管道&#xff08;|&#xff09; 1. 什么是管道&#xff08;Pipe&#xff09;&#xff1f; 管道&#xff08;|&#xff09;是 Unix/Linux Shell 中最强大的功能之一&#xff0c;它允许将一个命令的输出作为另一个命令的输入&#xff0c;从而实现数据流的处…...

[MySQL]事务的理论、属性与常见操作

目录 一、事物的理论 1.什么是事务 2.事务的属性&#xff08;ACID&#xff09; 3.再谈事务的本质 4.为什么要有事务 二、事务的操作 1.事务的支持版本 2.事务的提交模式 介绍 自动提交模式 手动提交模式 3.事务的操作 4.事务的操作演示 验证事务的回滚 事务异常…...

RS485接口EMC

A.滤波设计要点 L1为共模电感&#xff0c;共模电感能够衰减共模干扰&#xff0c;对单板内部的干扰以及外部的干扰都能抑制&#xff0c;能提高产品的抗干扰能力&#xff0c;同时也能减小通过485信号线对外的辐射&#xff0c;共模电感阻抗选择范围为120Ω/100MHz ~2200Ω/100MHz…...

快速上手mybatis教程

基础知识 MyBatis 是一款优秀的持久层框架&#xff0c;其核心组件主要包括以下部分&#xff1a; SqlSession 作用&#xff1a;SqlSession 是 MyBatis 的核心接口&#xff0c;负责与数据库进行通信&#xff0c;执行 SQL 语句&#xff0c;并返回查询结果。它是 MyBatis 的一次会…...

本地部署DeepSeek-R1保姆级教程

近期&#xff0c;我国一款开源模型 DeepSeek-R1以低成本和高性能震撼了全球科技界。该模型的开源性使开发者能够在本地环境中部署和运行&#xff0c;提供了更高的灵活性和控制力。如果你也想在本地部署 DeepSeek-R1&#xff0c;可以参考以下完整的教程&#xff0c;涵盖Mac 版本…...

blender 相机参数

目录 设置相机参数&#xff1a; 3. 设置相机参数示例 4. 相机透视与正交 5. 额外的高级设置 设置相机参数&#xff1a; 设置渲染器&#xff1a; 外参转换函数 转换测试代码&#xff1a; 获取blender渲染外参&#xff1a; 设置相机参数&#xff1a; 3. 设置相机参数示…...

在GPIO控制器中,配置通用输入,读取IO口电平时,上拉和下拉起到什么作用

上下拉电阻作用 在通用输入的时候&#xff0c;也就是在读某个IO的电平的时候 一定要让IO口先保持一个电平状态&#xff0c;这样才能检测到不同电平状态。 如何保持电平状态&#xff1f; 1. 可以通过芯片内部的上下拉电阻&#xff0c;由于是弱上下拉一般不用 2. 硬件外界一个…...

Maven工程核心概念GAVP详解:从命名规范到项目协作的基石

Maven工程核心概念GAVP详解&#xff1a;从命名规范到项目协作的基石 一、GAVP是什么&#xff1f; 在Maven工程中&#xff0c;GAVP是四个核心属性的缩写&#xff1a;GroupId、ArtifactId、Version、Packaging。这组属性为项目在Maven仓库中提供了唯一标识&#xff0c;类似于“项…...

如何利用DeepSeek打造医疗领域专属AI助手?从微调到部署全流程解析

如何利用DeepSeek开源模型打造医疗领域专属AI助手&#xff1f;从微调到部署全流程解析 医疗人工智能正迎来爆发式增长&#xff0c;但在实际应用中&#xff0c;通用大模型往往存在医学知识不精准、诊断逻辑不严谨等问题。本文将手把手带您实现医疗垂直领域大模型的定制化训练&a…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...