【堆】Leetcode 295. 数据流的中位数【困难】

ops/2024/9/23 17:45:57/

数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。

  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10 -5次方 以内的答案将被接受。

示例 1:

输入
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

解题思路

  • 1、使用两个优先队列(PriorityQueue),一个最大堆用于存储数据流的前半部分,一个最小堆用于存储数据流的后半部分。
  • 2、维护两个堆,使得最大堆的大小等于或比最小堆的大小大1,这样中位数就可以直接从堆顶元素中获取。
  • 3、当新的元素加入数据流时,根据元素的大小,将其插入到最大堆或最小堆中,并调整两个堆,使得满足上述条件。

Java实现

 private PriorityQueue<Integer> maxHeap; // 存储较小一半的元素private PriorityQueue<Integer> minHeap; // 存储较大一半的元素public MedianFinder() {maxHeap = new PriorityQueue<>(Collections.reverseOrder());minHeap = new PriorityQueue<>();}public void addNum(int num) {if (maxHeap.isEmpty() || num <= maxHeap.peek()) {maxHeap.offer(num);} else {minHeap.offer(num);}// 平衡两个堆,使大堆的size == 小堆的size 或者 小堆的size+1if (maxHeap.size() > minHeap.size() + 1) {minHeap.offer(maxHeap.poll());} else if (minHeap.size() > maxHeap.size()) {maxHeap.offer(minHeap.poll());}}public double findMedian() {if (maxHeap.isEmpty() && minHeap.isEmpty()) {return 0;}if (maxHeap.size() == minHeap.size()) {return (maxHeap.peek() + minHeap.peek()) / 2.0;} else {return maxHeap.peek();}}

时间空间复杂度

  • 时间复杂度:

addNum方法的时间复杂度为O(log n),其中n为数据流中元素的个数,因为在插入元素时需要维护堆的平衡。
findMedian方法的时间复杂度为O(1),因为只需要获取堆顶元素即可。

  • 空间复杂度:

由于使用了两个优先队列,所以空间复杂度为O(n)。


http://www.ppmy.cn/ops/15652.html

相关文章

【网站项目】书籍销售系统小程序

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

类和对象(中)(构造函数、析构函数和拷贝构造函数)

1.类的六个默认成员函数 任何类在什么都不写时&#xff0c;编译器会自动生成以下6个默认成员函数。 //空类 class Date{}; 默认成员函数&#xff1a;用户没有显示实现&#xff0c;编译器会自动生成的成员函数称为默认成员函数 2.构造函数 构造函数 是一个 特殊的成员函数&a…

Echarts-丝带图

Echarts-丝带图 demo地址 打开CodePen 什么是丝带图&#xff1f; 丝带图是Power BI中独有额可视化视觉对象&#xff0c;它的工具提示能展示指标当期与下期的数据以及排名。需求&#xff1a;使用丝带图展示"2022年点播订单表"不同月份不同点播套餐对应订单数据。 …

Bootstrap弹框使用

Bootstrap 是一个流行的前端框架&#xff0c;它提供了许多预定义的组件&#xff0c;包括弹框&#xff08;modal&#xff09;。使用 Bootstrap 的弹框可以轻松地创建弹出窗口&#xff0c;用于显示信息、收集用户输入等。 下面是使用 Bootstrap 弹框的基本步骤&#xff1a; 1. …

【前端Vue】Vue3+Pinia小兔鲜电商项目第6篇:整体认识和路由配置,本资源由 收集整理【附代码文档】

Vue3ElementPlusPinia开发小兔鲜电商项目完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;认识Vue3&#xff0c;使用create-vue搭建Vue3项目1. Vue3组合式API体验,2. Vue3更多的优势,1. 认识create-vue,2. 使用create-vue创建项目,1. setup选项的写法和执行…

Vitis HLS 学习笔记--优化指令-ARRAY_PARTITION

目录 1. ARRAY_PARTITION 概述 2. 语法解析 2.1 参数解释 2.1.1 variable 2.1.2 type 2.1.3 factor 2.1.4 dim 2.2 典型示例 2.2.1 dim1 2.2.2 dim2 2.2.3 dim0 3. 实例演示 4. 总结 1. ARRAY_PARTITION 概述 ARRAY_PARTITION 指令中非常重要&#xff0c;它用于优…

基于B2C的网上拍卖系统——秒杀与竞价

点击下载源码和论文https://download.csdn.net/download/liuhaikang/89222887 课题背景及意义 随着网络的进一步普及和电子商务的高速发展&#xff0c;越来越多的人们开始在网络中寻求方便。网上网物具备了省时、省事、省心、高效等特点&#xff0c;从而受到越来越多人的欢迎。…

Flutter 上架如何解决 ITMS-91053 问题

最近&#xff0c;我的 Flutter App 发布到 TestFlight 后&#xff0c;就会收到一封邮件&#xff1a;The uploaded build for YOUR APP has one or more issues. 上面的邮件主要是说&#xff0c;我的 App 缺少了调用 API 的声明&#xff0c;以前从来没看到过&#xff0c;上网一查…