295. 数据流的中位数

news/2024/9/23 19:27:37/
295. 数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。例如 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 以内的答案将被接受。

list 存储 超时

java">class MedianFinder {List<Integer> list = new ArrayList<>();public MedianFinder() {}public void addNum(int num) {int i = list.size();while (i > 0) {if (num < list.get(i-1)) {i-=1;} else {break;}}if (i == list.size()) {list.add(num);} else {list.add(i, num);}}public double findMedian() {int l = list.size();if (l % 2 == 1) {return list.get(l/2);}return (list.get(l/2) + list.get(l/2-1)) / 2.0D;}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

最大最小堆

java">class MedianFinder {PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((a, b) -> b-a);PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>((a, b) -> a-b);public MedianFinder() {}public void addNum(int num) {if (maxHeap.isEmpty() || num < maxHeap.peek()) {maxHeap.offer(num);if (minHeap.size() + 1 < maxHeap.size()){minHeap.offer(maxHeap.poll());}}  else {minHeap.offer(num);if (minHeap.size() > maxHeap.size()) {maxHeap.offer(minHeap.poll());}}}public double findMedian() {if (maxHeap.size() > minHeap.size()) {return maxHeap.peek();}return (minHeap.peek() + maxHeap.peek()) / 2.0D;}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

http://www.ppmy.cn/news/1431948.html

相关文章

数字化校园引领未来

在当今科技日新月异的时代&#xff0c;数字化转型已成为各行各业的必然趋势&#xff0c;教育领域也不例外。随着信息技术的迅猛发展&#xff0c;数字化已经成为推动教育变革的重要力量&#xff0c;它不仅重塑了传统的教育模式&#xff0c;还为学生、教师以及整个教育生态系统带…

vi编辑器的用法linux中的vim编辑器大全

vim的介绍 vi 和 vim 命令是linux中强⼤的⽂本编辑器, 由于Linux系统⼀切皆⽂件&#xff0c;⽽配置⼀个服务就是在修改其配置⽂件的参数。 vim 编辑器是运维⼯程师必须掌握的⼀个⼯具, 没有它很多⼯作都⽆法完成。 其中有vi和vim两种 vi和vim的区别 Vim是Vi的升级版本&#…

XYCTF 部分wp及学习记录

1.ezmd5 根据题目提示 我们知道应该是要上传两张md5值相同的图片 根据原文链接&#xff1a;cryptanalysis - Are there two known strings which have the same MD5 hash value? - Cryptography Stack Exchange 把保存下来的图片上传一下 得到flag 2.ezhttp 根据原文链接&…

【ARM Trace32(劳特巴赫) 使用介绍 15 -- 通过 nRESE从CPU第一条指令开始Debug】

请阅读【嵌入式开发学习必备专栏 】 文章目录 Trace32 NRESETNRESET 作用nRESET 使用介绍JTAG 特定引脚控制CPU第一条指令开始进行 debug注意事项Trace32 NRESET 在 TRACE32 系统中,nRESET 是一个非常重要的概念,它直接关联到目标系统(通常是一个微处理器或微控制器)的硬件…

深度学习基础之《TensorFlow框架(12)—图片数据》

一、图像基本知识 1、如何转换图片文件 回忆&#xff1a;之前我们在特征抽取中讲过如何将文本处理成数据 思考&#xff1a;如何将图片文件转换成机器学习算法能够处理的数据&#xff1f; 我们经常接触到的图片有两种&#xff0c;一种是黑白图片&#xff08;灰度图&#xff09;…

使用 Python 创建森林地图

介绍 森林和植被一直是地球上人类生存的核心。它们提供我们呼吸的空气、我们吃的食物以及建造我们家园的材料。由于大量有趣的研究项目,有几个开源数据集说明了地球上森林和植被的分布。借助 Python 的魔力,我们可以获取这些数据集,分析它们,操作它们,并使用它们生成富有…

灯光3-静态光照烘焙技术

UNITY静态光照烘焙技术是一种用于实现高质量光照效果的技术。它通过在场景中预计算光照信息&#xff0c;并将其存储在纹理或数据结构中&#xff0c;以便在运行时进行渲染。这种技术可以提供更真实的光照效果&#xff0c;并且可以在较低的运行时成本下实现。 在UNITY中&#xf…

DBever SQL编辑器的高级应用:如何用变量快速查询

哈喽&#xff0c;大家好&#xff0c;我是木头左&#xff01; 一、DBever SQL编辑器简介 DBever是一款数据库管理工具&#xff0c;它支持多种数据库&#xff0c;如MySQL、SQL Server、Oracle等。其中&#xff0c;它的SQL编辑器功能非常强大&#xff0c;可以让更方便地进行SQL语…