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

堆----3.数据流的中位数

295. 数据流的中位数 - 力扣(LeetCode)

/**

    基础数据结构:

            大顶堆:完全二叉树,任一结点>=其左右孩子;小顶堆:完全二叉树,任一结点<=其左右孩子

    大体做法:

            同时使用一个大顶堆与一个小顶堆,在插入元素时进行限制。

            大顶堆元素最大值 <= 小顶堆元素最小值,且两堆元素相差个数不超过1

            若两堆元素个数相等,则中位数:大顶堆堆顶元素(大顶堆最大值)与小顶堆堆顶元素(小顶堆最小值)的平均数

            若大顶堆的元素更多,则中位数:大顶堆堆顶元素

            若小顶堆的元素更多,则中位数:小顶堆堆顶元素(此处插入方式不存在该情况)

    插入过程:

            首先插入元素时统一直接插入大顶堆(小顶堆也可以)

            再把大顶堆的堆顶元素(大顶堆最大元素)弹出,插入到小顶堆;(即先将元素插入大顶堆,再把大顶堆最大的元素移到小顶堆,实现了大顶堆元素最大值 <= 小顶堆元素最小值)

            此时进行判断,若小顶堆元素更多,则将小顶堆堆顶元素(小顶堆最小元素)弹出,插入到大顶堆中;

            (由于为了实现大顶堆元素最大值 <= 小顶堆元素最小值,将大顶堆的最大元素移到了小顶堆,此时必须要平衡两堆元素,否则元素会全部留在小顶堆中)

    注意事项:

            经过调整后要么两堆元素数量相等,要么大顶堆元素更多,不存在小顶堆元素更多的情况。

*/

/**基础数据结构:大顶堆:完全二叉树,任一结点>=其左右孩子;小顶堆:完全二叉树,任一结点<=其左右孩子大体做法:同时使用一个大顶堆与一个小顶堆,在插入元素时进行限制。大顶堆元素最大值 <= 小顶堆元素最小值,且两堆元素相差个数不超过1若两堆元素个数相等,则中位数:大顶堆堆顶元素(大顶堆最大值)与小顶堆堆顶元素(小顶堆最小值)的平均数若大顶堆的元素更多,则中位数:大顶堆堆顶元素若小顶堆的元素更多,则中位数:小顶堆堆顶元素(此处插入方式不存在该情况)插入过程:首先插入元素时统一直接插入大顶堆(小顶堆也可以)再把大顶堆的堆顶元素(大顶堆最大元素)弹出,插入到小顶堆;(即先将元素插入大顶堆,再把大顶堆最大的元素移到小顶堆,实现了大顶堆元素最大值 <= 小顶堆元素最小值)此时进行判断,若小顶堆元素更多,则将小顶堆堆顶元素(小顶堆最小元素)弹出,插入到大顶堆中;(由于为了实现大顶堆元素最大值 <= 小顶堆元素最小值,将大顶堆的最大元素移到了小顶堆,此时必须要平衡两堆元素,否则元素会全部留在小顶堆中)注意事项:经过调整后要么两堆元素数量相等,要么大顶堆元素更多,不存在小顶堆元素更多的情况。
*/
class MedianFinder {//大顶堆,左半区,存较小的元素private PriorityQueue<Integer> left_maxHeap;//小顶堆,右半区,存较大的元素private PriorityQueue<Integer> right_minHeap; public MedianFinder() {//优先队列实现大/小顶堆left_maxHeap = new PriorityQueue<>((a,b) -> b - a); //大顶堆,自定义比较器right_minHeap = new PriorityQueue<>(); //默认为小顶堆}public void addNum(int num) {//直接插入大顶堆left_maxHeap.offer(num);//保证 大顶堆元素最大值 <= 小顶堆元素right_minHeap.offer(left_maxHeap.poll());//平衡两堆元素个数 要么两堆元素个数相等,要么大顶堆比小丁堆多一个元素if(right_minHeap.size() > left_maxHeap.size()) {left_maxHeap.offer(right_minHeap.poll());}}public double findMedian() {//两堆元素相等 大顶堆堆顶元素(大顶堆最大值)与小顶堆堆顶元素(小顶堆最小值)的平均值if(right_minHeap.size() == left_maxHeap.size()) {return (right_minHeap.peek() + left_maxHeap.peek()) / 2.0;} //要么两堆元素个数相等,要么大顶堆比小顶堆多一个元素return left_maxHeap.peek();}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

http://www.lryc.cn/news/615139.html

相关文章:

  • 【Redis】Redis-plus-plus的安装与使用
  • 自定义通知组件跟随右侧边栏移动
  • SQL基本
  • 探索Trae:使用Trae CN爬取 Gitbook 电子书
  • 2025-08-09 李沐深度学习14——经典卷积神经网络 (2)
  • 生态问题是什么?
  • P1890 gcd区间
  • 如何理解SA_RESTART”被信号中断的系统调用自动重启“?
  • SELinux 入门指南
  • ROS2 多线程 与组件机制
  • Python NumPy入门指南:数据处理科学计算的瑞士军刀
  • Qt 的对象线程亲和性规则
  • 华为欧拉OpenEnler系统在启动MindIE时权限问题的解决方法
  • 从灵感枯竭到批量产出:无忧秘书创作平台如何重构内容生产者的工作流程?全环节赋能分析
  • Spring Boot 集成 Quartz 实现定时任务(Cron 表达式示例)
  • WinForm 中 ListView 控件的实战应用与功能拓展
  • kafka架构原理快速入门
  • AI大语言模型在生活场景中的应用日益广泛,主要包括四大类需求:文本处理、信息获取、决策支持和创意生成。
  • 软件定义车辆加速推进汽车电子技术
  • Blender 快捷键速查表 (Cheat Sheet)
  • 【线性代数】6二次型
  • 可直接运行的 Playwright C# 自动化模板
  • 通过 Certimate 统一管理 SSL 证书 支持自动化申请、全平台部署
  • 【线性代数】线性方程组与矩阵——(1)线性方程组与矩阵初步
  • 数据挖掘2.6 Perceptron Modeling 感知器建模
  • 我想做自动化报社保,用哪种技术更好一点呢?
  • stm32项目(25)——基于stm32的植物生长箱环境监测系统
  • 「iOS」————响应者链与事件传递链
  • GPT-5:数字大脑的进化史
  • 人工智能-python-数据处理实战-特征降维(PCA)