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

⭐算法OJ⭐数据流的中位数【最小堆】Find Median from Data Stream

news 来源：原创 2025/9/21 7:12:02

最小堆

最小堆是一种特殊的完全二叉树数据结构。

基本定义

堆性质：每个节点的值都小于或等于其子节点的值（根节点是最小值）
完全二叉树性质：除了最底层外，其他层的节点都是满的，且最底层的节点都靠左排列

关键特性

根节点最小：堆顶元素始终是堆中的最小值
高效操作：
- 获取最小值： $O (1)$
- 插入元素： $O (l o g n)$
- 删除最小值： $O (l o g n)$

实现方式

最小堆通常用数组实现，利用数组索引表示树结构：

对于索引 i 的元素：
- 父节点索引：(i-1)/2
- 左子节点索引：2i+1
- 右子节点索引：2i+2

问题描述

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within $10^{-5}$ of the actual answer will be accepted.

Example:

Input

["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]

Output

[null, null, null, 1.5, null, 2.0]

Explanation

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

问题描述

设计一个数据结构，能够支持以下两种操作：

addNum(int num) - 向数据结构中添加一个整数
findMedian() - 返回当前所有元素的中位数

如果元素数量是奇数，中位数是最中间的数；如果是偶数，中位数是中间两个数的平均值。

方法思路

数据结构

我们可以使用两个堆来高效解决这个问题：

一个最大堆max_heap存储较小的一半数字
一个最小堆min_heap存储较大的一半数字

这样设计可以保证：

最大堆的堆顶是较小一半数字中的最大值
最小堆的堆顶是较大一半数字中的最小值
两个堆的大小保持平衡（大小相等或最大堆比最小堆多1）

`addNum` 操作：

先将新数字加入最大堆
然后将最大堆的堆顶（当前最大值）移到最小堆
最后检查并平衡两个堆的大小，确保最大堆的大小不小于最小堆

`findMedian` 操作：

如果最大堆比最小堆多一个元素，返回最大堆的堆顶
否则返回两个堆顶的平均值

解决代码

#include <queue>
#include <vector>using namespace std;class MedianFinder {
private:priority_queue<int> max_heap; // 存储较小的一半，最大堆priority_queue<int, vector<int>, greater<int>> min_heap; // 存储较大的一半，最小堆public:MedianFinder() {}void addNum(int num) {// 先将数字加入最大堆max_heap.push(num);// 将最大堆的最大值移到最小堆min_heap.push(max_heap.top());max_heap.pop();// 平衡两个堆的大小if (max_heap.size() < min_heap.size()) {max_heap.push(min_heap.top());min_heap.pop();}}double findMedian() {if (max_heap.size() > min_heap.size()) {return max_heap.top();} else {return (max_heap.top() + min_heap.top()) / 2.0;}}
};

复杂度分析

addNum： $O (l o g n)$ ，因为堆的插入和删除操作都是对数时间复杂度
findMedian： $O (1)$ ，只需要访问堆顶元素

这种方法巧妙地利用了两个堆的性质，使得我们可以在对数时间内添加元素，常数时间内找到中位数。

⭐算法OJ⭐数据流的中位数【最小堆】Find Median from Data Stream

最小堆最小堆是一种特殊的完全二叉树数据结构。基本定义堆性质：每个节点的值都小于或等于其子节点的值（根节点是最小值）完全二叉树性质：除了最底层外，其他层的节点都是满的，且最底层的节点都靠左排列…...

编程日记 2025/9/21 7:12:02

node-modules-inspector 使用以及 node_modules可视化依赖关联关系快速分析

node-modules-inspector 使用以及 node_modules可视化依赖关联关系快速分析 node-modules-inspector 简介 node-modules-inspector 是一个用于分析和可视化 node_modules 依赖关系的工具，主要功能包括： 依赖可视化：以交互式图表展示项目的依…...

编程日记 2025/9/18 23:29:39

python自动登录远程设备的几种方式（华为设备）

其实登录远程设备（交换机路由器）的方式无非就是通过SSH或者是Telnet这两个协议，当然最主要的还是SSH，这里主要讲的是通过这两个协议登录远程设备的几个方式拓扑本文都是用的这个拓扑，主要通过编写python脚本来登录其…...

编程日记 2025/9/20 17:17:58

【android bluetooth 框架分析 01】【关键线程 1】【关键线程介绍】

1. 为什么学习蓝牙协议栈之前，必须先梳理清楚这几大线程？ 为什么学习协议栈之前最好是要先梳理清楚关键线程 bt_stack_manager_threadbt_jni_threadbt_main_threadbt_a2dp_sink_worker_thread 1.1 蓝牙协议栈是典型的“多线程异步系统” 蓝牙协议…...

编程日记 2025/9/12 22:20:26

LDAP高效数据同步：Syncrepl复制模式实战指南

#作者：朱雷文章目录一、Syncrepl 复制简介1.1. 什么是复制模式1.2. 什么是 syncrepl同步复制二、Ldap环境部署三、配置复制类型3.1. 提供者端配置3.2. 消费者端配置3.3.启动服务3.4.测试同步是否生效四、总结一、Syncrepl 复制简介 1.1. 什么是复制模式 Ope…...

编程日记 2025/9/12 6:14:08

SeeGround: See and Ground for Zero-Shot Open-Vocabulary 3D Visual Grounding

CVPR 2025 核心问题与动机问题背景：3D视觉定位（3DVG）要求根据文本描述在3D场景中定位目标物体，是增强现实、机器人导航等应用的关键技术。传统方法依赖标注的3D数据集和预定义类别，限制了其在开放场景中的扩展性。现…...

编程日记 2025/9/16 4:57:48

深入理解Spring IoCDI

1. 引言：为什么需要IoC和DI？ 传统开发方式的耦合性问题在传统开发中，对象通常通过 new 关键字直接创建，例如： // 直接依赖具体实现类 UserService userService new UserServiceImpl(); OrderService orderService…...

编程日记 2025/9/18 13:36:47

NO.78十六届蓝桥杯备战|数据结构-并查集|双亲表示法|初始化|查询|合并|判断|亲戚|Lake Counting|程序自动分析(C++)

双亲表⽰法接下来要学习到的并查集，本质上就是⽤双亲表⽰法实现的森林。因此，我们先认识⼀下双亲表⽰法。在学习树这个数据结构的时，讲到树的存储⽅式有很多种：孩⼦表⽰法，双亲表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表…...

编程日记 2025/9/11 15:02:07

20250407-组件v-model

基本用法 v-model 可以在组件上使用以实现双向绑定。首先看下 v-model 在原生元素上的用法： <input v-model"searchText" /> 在代码背后，模板编译器会对 v-model 进行更冗长的等价展开。因此上面的代码其实等价于下面这段&#xff…...

编程日记 2025/8/30 7:59:56

oracle 存储体系结构

oracle 存储体系结构参考： Logical Storage Structures (oracle.com)...

编程日记 2025/9/6 11:28:27

晋城市电子健康证上传照片尺寸要求及手机拍照制作方法

晋城市餐饮从业人员健康证电子照片上传有着明确的技术规范。根据"晋城市从业人员电子健康证明服务平台"要求，照片尺寸应为358像素（宽）441像素（高），这一比例符合标准证件照的规格。照片底色可选择…...

编程日记 2025/9/11 7:17:44

STL c++ list——模拟实现

结点类的模拟实现 list是一个带头双向循环链表因需要实现一个节点类，其中包含哨兵位（用来标识位置），节点信息（val数据，prev后指针，next后指针） template<class T> struct …...

编程日记 2025/8/29 17:58:08

【ES系列】Elasticsearch从入门到精通保姆级教程 | 启篇

🔥 本系列将带你从零开始学习Elasticsearch，通过保姆级教程，手把手教你掌握这个强大的搜索与分析引擎。无论你是完全的新手，还是想系统学习ES的开发者，这个系列都能满足你的需求。 📚博主匠心之作，强推专栏： JAVA集合专栏【夜话集】JVM知识专栏数据库sql理论与实战【…...

编程日记 2025/9/20 11:39:47

图解Java运行机制-JVM、JRE、JDK区别

以下是Java运行机制及JVM、JRE、JDK区别的图解与说明： --- ### 一、Java程序运行机制 1. **编写与编译** Java源文件（.java）通过**JDK中的编译器（javac）**编译为字节码文件（.class）&#xff…...

编程日记 2025/9/18 20:22:46

UML类图综合实验三补档

1.使用简单工厂模式模拟女娲(Nvwa)造人(Person)，如果传入参数“M”，则返回一个Man对象，如果传入参数“W”，则返回一个Woman对象，用Java语言实现该场景。现需要增加一个新的Robot类，如果传入参数“R”&#…...

编程日记 2025/9/19 18:49:58

OpenHarmony子系统开发 - DFX（八）

OpenHarmony子系统开发 - DFX（八） 八、Faultlogger开发指导概述功能简介 Faultlogger是OpenHarmony为开发者提供的一个维测日志框架，能够为应用、元能力、系统服务进程崩溃故障提供统一检测、日志采集、日志存储、日志上报功能&#xf…...

编程日记 2025/9/18 19:30:56

C# virtual 和 abstract 详解

简介在 C# 中，virtual 和 abstract 关键字都用于面向对象编程中的继承和多态，它们主要用于方法、属性和事件的定义，但在用法上存在一些重要的区别。 virtual 关键字 virtual 表示可重写的方法，但可以提供默认实现，…...

编程日记 2025/9/17 15:16:05

红宝书第三十二讲：零基础学会模块打包器：Webpack、Parcel、Rollup

红宝书第三十二讲：零基础学会模块打包器：Webpack、Parcel、Rollup 资料取自《JavaScript高级程序设计（第5版）》。查看总目录：红宝书学习大纲一、模块打包器是什么？ 把分散的HTML/CSS/JS文件组合成浏览…...

编程日记 2025/9/15 13:03:35

DeepSeek 在金融领域的应用解决方案

DeepSeek 在金融领域的应用解决方案一、背景随着人工智能技术的快速发展，DeepSeek 作为一款国产大模型，凭借其强大的语义理解、逻辑推理和多模态处理能力，在金融行业迅速崭露头角。金融行业作为经济的核心，面临着激烈的市场竞…...

编程日记 2025/9/16 3:52:40

linux 处理2个文件的差集

命令 grep -Fvxf 文件1 文件2 -F 将模式视为固定字符串，而非正则表达式。 -v 反向匹配，输出不匹配的行。 -x 精确匹配整行，避免部分匹配。 -f 文件1 从文件1中读取模式。示例执行命令 grep -Fvxf a1.txt a2.txt...

编程日记 2025/9/3 0:41:31

vue3中pinia基本使用

一、安装以及引入安装：npm install piniamain.js文件： import { createApp } from "vue"; import { createPinia } from "pinia"; import App from "./App.vue";const pinia createPinia() const app createApp(App)…...

编程日记 2025/9/10 6:04:47

“乐企“平台如何重构业财税票全流程生态？

2025年，国家税务总局持续推进的"便民办税春风行动"再次推进数字化服务升级，其中"乐企"平台作为税务信息化的重要载体，持续优化数电票服务能力，为企业提供更高效、更规范的税务管理支持。在这一背景下&#xf…...

编程日记 2025/9/11 18:26:06

JVM内存模型

JVM内存模型 JVM（Java Virtual Machine）内存模型是 Java 程序在运行时，JVM 为其分配的内存结构，它定义了 Java 程序如何在内存中存储数据和如何进行线程之间的通信。JVM 内存模型是为了支持高效的多线程执行和垃圾回收机制。一…...

编程日记 2025/9/18 15:11:07

LeetCode热题100记录-【二分查找】

二分查找 35.搜索插入位置思考：二分查找先判定边界条件记录：不需要二刷 class Solution {public int searchInsert(int[] nums, int target) {int left 0,right nums.length-1;if(nums[right] < target){return right1;}if(nums[left] > tar…...

编程日记 2025/9/8 8:20:43

科普：原始数据是特征向量么?

一、输入向量 x \mathbf{x} x是特征向量机器学习算法公式中的输入向量 x \mathbf{x} x通常要求是特征向量。原因如下： 从算法原理角度：机器学习算法旨在通过对输入数据的学习来建立模型，以实现对未知数据的预测或分类等任务。特征向量是对…...

编程日记 2025/9/18 22:17:24

1.完整代码 chartsOption: {tooltip: {trigger: "item",formatter: this.initTooltip,triggerOn: "mousemove",borderColor: "#fff",backgroundColor: "rgba(216, 227, 244, 1)",extraCssText: "border-radius: 14px;", //…...

编程日记 2025/9/20 13:04:24

Linux(十三）fork + exec进程创建

一、进程创建在了解进程创建的步骤前，让我们先通过实例观察一下。大家可以跟小编一起，在终端中执行3次ps -f命令，观察一下。通过上图，我们可以发现，3次ps -f的父进程（PPID）都是一样的&#xf…...

编程日记 2025/9/12 7:21:51

集合计算高级函数

说明过滤遍历一个集合并从中获取满足指定条件的元素组成一个新的集合转化/映射（map）将集合中的每一个元素映射到某一个函数扁平化扁平化映射注：flatMap 相当于先进行 map 操作，在进行 flatten 操作集合中的每个元素的子元素映…...

编程日记 2025/9/17 14:22:27

鼎讯信通便携式雷达信号干扰模拟器：打造实战化电磁环境的新利器

在现代战争中，电磁环境的复杂性直接影响着雷达装备的性能和作战效果。面对敌方日益精进的电子战手段，如何提升雷达设备的抗干扰能力，确保其在实战环境中的稳定性和可靠性，已成为各国军队和科研机构的重要课题。为此，…...

编程日记 2025/9/10 10:54:06

避开养生误区，拥抱健康生活

在追求健康的道路上，我们常常会陷入一些养生误区，不仅无法达到预期效果，还可能损害身体健康。只有拨云见日，认清这些误区，采取正确的养生方式，才能真正拥抱健康生活。很多人认为，保健品吃得…...

编程日记 2025/9/19 8:43:18

解码ChatBI技术形态：独立对话框、插件式与IM集成模式的技术优劣

ChatBI的形态之争随着大语言模型（LLM）技术的成熟，**对话式商业智能（ChatBI）**正成为企业数据分析的新范式。然而，不同的技术形态直接影响ChatBI的落地效果——独立对话框、插件式助手、IM集成机器人&…...

编程日记 2025/9/19 9:45:59

rockylinux 8 9 升级到指定版本

rockylinux 8 update 指定版本 rockylinux 历史版所有版本rockylinux 最新版所有版本vault历史版 pub最新版(https://dl.rockylinux.org)地址后面增加不同名称 echo "delete repos" rm -rf /etc/yum.repos.d/*echo "new rockylinux repo" cat <<EO…...

编程日记 2025/9/18 11:02:49

一文详解OpenCV环境搭建：Ubuntu20.4使用CLion配置OpenCV开发环境

在计算机视觉和图像处理领域，OpenCV 是一个不可或缺的工具。其为开发者提供了一系列广泛的算法和实用工具，支持多种编程语言，并且可以在多个平台上运行。对于希望在其项目中集成先进视觉功能的开发者来说，掌握如何配置和使用OpenC…...

编程日记 2025/9/16 4:29:28

Android Coli 3 ImageView load two suit Bitmap thumb and formal，Kotlin（四）

Android Coli 3 ImageView load two suit Bitmap thumb and formal，Kotlin（四） 对 Android Coli 3 ImageView load two suit Bitmap thumb and formal，Kotlin（三）-CSDN博客进行完善，注意完善 …...

编程日记 2025/9/20 5:12:05

01-JVM 内存模型与 GC 原理

JVM 内存模型与 GC 原理解析本文将从 JVM 内存模型入手，深入剖析各个区域的作用、GC 的运行机制与常见算法，并结合源码与面试思维，带你掌握 JVM 的底层世界。一、JVM 内存模型（Java Memory Model） JVM 将内存划分为…...

编程日记 2025/9/18 18:19:25

Docker--Docker镜像制作的注意事项

Docker 镜像制作 dockerfiles的指令讲解链接 CMD和ENTRYPOINT CMD 和 ENTRYPOINT 是 Dockerfile 中用于指定容器启动时运行命令的两个指令。它们在功能上有一些相似之处，但也存在重要区别。在编辑Dockerfile时，ENTRYPOINT或者CMD命令会自动覆盖之前…...

编程日记 2025/9/19 17:29:13

AI：支持向量机（SVM）

支持向量机（SVM）理论基础详解：从零开始的完全指南一、SVM的核心思想：直观理解 1.1 什么是分类问题？想象你在玩一个游戏：桌上有红色和蓝色的球，你需要画一条线把它们分开。这条线就是分类边界。SVM的目标是找到一条最优分界线，使得这条线到最近的红色球和蓝色球的距…...

编程日记 2025/9/11 1:16:31

Vue.js 中 v-if 的使用及其原理

在 Vue.js 的开发过程中，条件渲染是一项极为常见的需求。v-if指令作为 Vue.js 实现条件渲染的关键手段，能够根据表达式的真假来决定是否渲染某一块 DOM 元素。它在优化页面展示逻辑、提升用户体验等方面发挥着重要作用。接下来，我们就深入探讨…...

编程日记 2025/9/19 19:02:16

Vue.js 中 v-show 的使用及其原理

在 Vue.js 的开发过程中，我们常常需要根据不同的条件来控制页面元素的显示与隐藏。v-show指令作为 Vue.js 提供的重要工具之一，为我们实现这一功能提供了便捷的途径。它与v-if指令有些相似，但在使用方法和原理上存在着明显的区别。接下来&…...

编程日记 2025/9/4 22:41:25

docker安装redisSearch

1.背景 Redis Search 是 Redis 官方提供的全文搜索引擎,它为Redis 提供全文搜索、索引和复杂查询功能。它基于内存存储，结合了 Redis 的高性能和倒排索引技术，支持实时搜索、聚合分析、模糊匹配等场景。RedisSearch 适用于需要快速检索结构化或非结构化…...

编程日记 2025/9/20 5:12:23

ADI的BF561双核DSP怎么做开发，我来说一说（六）IDE硬盘设计

作者的话 ADI的双核DSP，最早的一颗是Blackfin系列的BF561，这颗DSP我用了很久，比较熟悉，且写过一些给新手的教程。是的你没有看错，就是IDE，那个最老的硬盘，我们当年做过此类设计。硬件准备 …...

编程日记 2025/9/10 1:29:15

5.数据结构-图

5.数据结构-图 5.1 图的定义和基本术语5.1.1 图的定义5.1.2 图的基本术语 5.2图的存储结构5.2.1邻接矩阵采用邻接矩阵表示法创建无向网邻接表 5.1 图的定义和基本术语 5.1.1 图的定义图 G由两个集合V和E组成，记为 G ( V , E ) G(V,E) G(V,E)，其中V是…...

编程日记 2025/9/9 17:52:35

uni-app使用web-view传参的坑

问题描述 uni-app开发的一个页面，需要点击时跳转到PC端后台的一个详情页，所以需要传参如下： ticketIdticketCodetoken（用于自动登录，校验身份的） 但是吧，如果你明文传token，容易导…...

编程日记 2025/9/11 11:16:17

Android studio打包uniapp插件

一.参考资料与环境准备原生工程配置需要使用到Android studio和HbuilderX 当前测试的as版本-20240301,下载地址：HbuilderX版本：4.36 二.插件创建流程 1.导入下载的UniPlugin-Hello-AS工程（下载地址见参考资料） 2.生成jks证书…...

编程日记 2025/9/19 17:19:23

SVT-AV1学习-函数selfguided_restoration_fast_internal

一 selfguided_restoration_fast_internal 函数作用 selfguided_restoration_fast_internal是SVT-AV1 编码器中用于自引导恢复Guided Resration SGR 的一个内部函数，通过自引导滤波技术对输入的去燥他图像数据进行处理，生成一个去燥版本的图像&#xff0…...

编程日记 2025/9/16 6:00:14

双引擎驱动：解密音视频体验的QoS技术底座与QoE感官革命

QoS 定义：QoS（Quality of Service，服务质量）衡量音视频传输技术层面的性能表现，聚焦网络传输和系统处理能力，通过客观指标量化服务质量。核心指标码率/带宽：数据传输速率上限，直接…...

编程日记 2025/9/6 4:48:19

element-plus选择菜单栏不变色

代码： <template> ... <el-menu-item index"/task/execute"><el-icon><IconMenu /></el-icon><span>验收任务</span> </el-menu-item> <el-menu-item index"/task/change"><el-icon…...

编程日记 2025/9/21 4:32:36

uniapp加载json动画

一、添加canvas画布 <canvas id"lottie_demo" type"2d" style"display: inline-block;width: 148rpx; height: 148rpx;" /> 二、引入依赖和JSON文件安装依赖 npm install lottie-miniprogram --save import lottie from lottie-mini…...

编程日记 2025/9/19 5:40:30

快递物流展同期举办2025中国智慧物流核心零部件创新论坛

2025中国智慧物流核心零部件创新论坛会议主题：“AI ”重构智慧物流核心技术生态会议介绍随着人工智能、物联网、5G等技术的快速发展，智慧物流已成为全球物流行业转型升级的核心方向。在AI技术的驱动下，物流行业正从传统的“人、车、货”…...

编程日记 2025/9/12 14:32:03

ASP.NET图书馆借阅系统(源码+lw+部署文档+讲解)，源码可白嫖!

摘要近些年来，随着科技的飞速发展，互联网的普及逐渐延伸到各行各业中，给人们生活带来了十分的便利，图书馆借阅系统利用计算机网络实现信息化管理，使图书信息、图书借阅、归还的管理发展和服务水平有显著提升。本文拟…...

编程日记 2025/9/8 1:08:56

最小堆

基本定义

关键特性

实现方式

问题描述

问题描述

方法思路

数据结构

addNum 操作：

findMedian 操作：

解决代码

复杂度分析

相关文章：

`addNum` 操作：

`findMedian` 操作：