算法通过村第十四关-堆|黄金笔记|中位数

文章目录

  • 前言
  • 数据流中的中位数的问题
  • 总结


前言


提示:我独自度过了太多的时光,沉默已成一种习惯。 帕瑞尔·马卡姆《夜航西飞》

这个是一个比较难的题目,要不尝试一下看看。

数据流中的中位数的问题

参考题目地址:295. 数据流的中位数 - 力扣(LeetCode)

在这里插入图片描述
在这里插入图片描述

进阶问题:

  1. 如果数据流中所有整数都在0到100范围内呢,你将如何优化你的算法?
  2. 如果数据流中99%的整数都在0到100范围内呢?你将如何优化你的算法?

我们分析一下:

这道题说真的挺难的,如果没有专门的学过,很难再面试中想到。

中位数的题目,我们一般可以采用 大顶堆 + 小顶堆 来求解,下面我们通过直观的例子了解下怎么处理:

小顶堆:存储所有元素中较大的一半,堆顶存储的其实是最小的数。

大顶堆:存储所有元素中较小的一半,堆顶存储的其实是最大的数。

相当于,把所有元素分成大小两半,而我们计算中位数,只需要大的那半的最小值和小的那半的最大值就可以了。

比如:我们依次添加【1,2,3,4,5】,砍成两半为【1,2】和【3,4,5】。我们是需要快速找到 2 和 3 就可以了。

下面我们看看两个堆是怎么变化的:

  1. 添加1,进入minHeap中,中位数为1
  2. 添加2 ,它比minHeap堆顶的元素大1,进入minHeap,minHeap中的元素超过所有元素总和的一半,所以要平衡一下,分给maxHeap,中位数为(1 + 2 )/ 2 = 1.5;
  3. 添加 3 ,它比minHeap堆顶元素2 大,进入minHeap,中位数为2;
  4. 添加4 ,它比minHeap堆顶的元素2大,进入minHeap,minHeap中的元素超过所有元素总和的一半,所以要平衡一下,分给maxHeap,中位数为(2+ 3 )/ 2 = 2.5;
  5. 添加 5,它比minHeap堆顶元素3 大,进入minHeap,中位数为3;

Java中堆(即使优先队列)是使用完全二叉树实现的。理解以下,我们看代码怎么做,代码写起来比较简单,但是实现起来还挺麻烦的。

class MedianFinder {// 这里小顶堆 存储较大的一半(最小值在堆顶PriorityQueue<Integer> minHeap;// 这里大顶堆 存储较小的一半(最大值在堆顶PriorityQueue<Integer> maxHeap;public MedianFinder() {minHeap = new PriorityQueue<>();maxHeap = new PriorityQueue<>((a,b) -> b - a);}public void addNum(int num) {// 小顶堆存储大的元素,num只要大于元素中最小的,就入堆if(minHeap.isEmpty() || num > minHeap.peek()){minHeap.offer(num);if(minHeap.size() - maxHeap.size() > 1){maxHeap.offer(minHeap.poll());}}else{maxHeap.offer(num);// 可以确保多的那个元素一定在minHeapif(maxHeap.size() - minHeap.size() > 0){minHeap.offer(maxHeap.poll());}}}public double findMedian() {if(minHeap.size() > maxHeap.size()){return minHeap.peek();}else if(minHeap.size() < maxHeap.size()){return maxHeap.peek();}else{return (minHeap.peek() + maxHeap.peek()) / 2.0;}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

总结

提示:堆的经典应用;大顶堆小顶堆;中位数问题;特殊解法;优先队列(priority):


如果有帮助到你,请给题解点个赞和收藏,让更多的人看到 ~ ("▔□▔)/ 如有不理解的地方,欢迎你在评论区给我留言,我都会逐一回复 ~ 也欢迎你 关注我 ,喜欢交朋友,喜欢一起探讨问题。

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/161255.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MyBatisPlus-02

一 查询条件的三种 1.按条件查询 //方式一&#xff1a;按条件查询QueryWrapper qw new QueryWrapper();qw.lt("age",18);List<User> userList userDao.selectList(qw);System.out.println(userList); 2.lambda格式按条件查询 //方式二&#xff1a;lambda格…

基于EtherCAT的机器人多轴同步运动控制

随着工业自动化的发展&#xff0c;机器人在生产线上的应用越来越广泛。为了实现高效、精确的运动控制&#xff0c;机器人的多轴运动必须能够实现同步操作&#xff0c;它能够提高机器人的运动精度和稳定性&#xff0c;实现更高效的生产线操作。同时&#xff0c;它也为机器人的协…

WebGPU入门一

1 WebGPU学习开发环境配置 WebGPU的环境配置比较简单&#xff0c;不需要vite或webpack配置一个复杂的开发环境&#xff0c;直接使用.html文件即可。 1.1 支持WebGPU的浏览器 Chrome 113 beta测试版开始默认支持WebGPU。 1.2 index.html文件 创建index.html文件&#xff0c…

C++进阶篇1---继承

一、继承的概念和定义 1.1概念 继承机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c;它允许程序员在保持原有类特性的基础上进行扩展&#xff0c;增加功能&#xff0c;这样产生新的类&#xff0c;称为派生类。继承呈现了面向对象程序设计的层次结构&#xff…

ExoPlayer架构详解与源码分析(5)——MediaSource

系列文章目录 ExoPlayer架构详解与源码分析&#xff08;1&#xff09;——前言 ExoPlayer架构详解与源码分析&#xff08;2&#xff09;——Player ExoPlayer架构详解与源码分析&#xff08;3&#xff09;——Timeline ExoPlayer架构详解与源码分析&#xff08;4&#xff09;—…

掌握Python爬虫实现网站关键词扩展提升曝光率

目录 一、关键词优化的重要性 二、关键词优化的基本方法 1、选择与网站内容相关的关键词 2、控制关键词的密度和分布 3、关键词的层次布局 三、Python爬虫实现网站关键词扩展 1、确定目标网站 2、分析目标网站的HTML结构 3、编写Python爬虫代码 4、分析爬取到的关键词…

【算法练习Day22】 组合总和 III电话号码的字母组合

​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;练题 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录 组合总和 III剪枝 电话号码…

深入理解React中的useEffect钩子函数

引言&#xff1a; React是一种流行的JavaScript库&#xff0c;它通过组件化和声明式编程的方式简化了前端开发。在React中&#xff0c;一个核心概念是组件的生命周期&#xff0c;其中包含了许多钩子函数&#xff0c;用于管理组件的不同阶段。其中之一就是useEffect钩子函数&…

LuaJit交叉编译移植到ARM Linux

简述 Lua与LuaJit的主要区别在于LuaJIT是基于JIT&#xff08;Just-In-Time&#xff09;技术开发的&#xff0c;可以实现动态编译和执行代码&#xff0c;从而提高了程序的运行效率。而Lua是基于解释器技术开发的&#xff0c;不能像LuaJIT那样进行代码的即时编译和执行。因此&…

系统架构与Tomcat的安装和配置

2023.10.16 今天是学习javaweb的第一天&#xff0c;主要学习了系统架构的相关知识和原理&#xff0c;下载了web服务器软件&#xff1a;Tomcat&#xff0c;并对其进行了配置。 系统架构 包括&#xff1a;C/S架构 和 B/S架构。 C/S架构&#xff1a; Client / Server&#xff0…

离散数学 学习 之 递推方程和生成函数

递推方程 注意这里的特征根一定不是相等 特解的话一般要去设出基本的形式 这是0 次多项式 生成函数

【JAVA】集合与背后的逻辑框架,包装类,List,Map,Set,静态内部类

❤️ Author&#xff1a; 老九 ☕️ 个人博客&#xff1a;老九的CSDN博客 &#x1f64f; 个人名言&#xff1a;不可控之事 乐观面对 &#x1f60d; 系列专栏&#xff1a; 文章目录 collectionCollection创建collection使用泛型collection方法 Map 接口Map的存储结构HashMap和Tr…

lenovo联想笔记本ThinkPad系列T15p或P15v Gen3(21DA,21DB,21D8,21D9)原厂Win11系统镜像

下载链接&#xff1a;https://pan.baidu.com/s/1V4UXFhYZUNy2ZQ8u4x1AFg?pwdqz0s 系统自带指纹驱动、人脸识别驱动、显卡、声卡等所有驱动、出厂主题壁纸、Office办公软件、Lenovo联想电脑管家等预装程序 所需要工具&#xff1a;32G或以上的U盘 文件格式&#xff1a;ISO …

一篇文章带你搞定所有二叉树题型的递归思维(思路超详细)

文章目录 &#x1f380;前言&#xff1a;&#x1f3c5;先在开头总结一下&#xff0c;二叉树解题的思维模式分两类&#xff1a;&#x1f387;先解释一下“前序位置”&#xff0c;“后序位置”的意思&#x1f3e8;举一个简单的例子&#xff1a; &#x1fa80;下面通过两道例题&am…

从自动化到测开,测试人员逆袭之路从此起步

在当今竞争激烈的软件测试行业中&#xff0c;近期的招聘市场确实面临一些挑战。大量的求职者争相涌入岗位&#xff0c;许多热衷于功能测试的人士甚至难以找到理想的工作机会。更不幸的是&#xff0c;连自动化测试和性能测试这些专业领域也受到了测试开发人员的竞争压力。然而&a…

C# 图解教程 第5版 —— 第4章 类型、存储和变量

文章目录 4.1 C# 程序是一组类型声明4.2 类型是一种模板&#xff08;*&#xff09;4.3 实例化类型4.4 数据成员和函数成员4.5 预定义类型4.6 用户定义类型4.7 堆和栈&#xff08;*&#xff09;4.8 值类型和引用类型4.9 变量4.9.1 变量声明4.9.2 多变量声明&#xff08;*&#x…

模式植物背景基因集制作

一边学习&#xff0c;一边总结&#xff0c;一边分享&#xff01; 写在前面 关于GO背景基因集文件的制作&#xff0c;我们在很早以前也发过。近两天&#xff0c;自己在分析时候&#xff0c;也是被搞了头疼。想重新制作一份GO背景基因集&#xff0c;进行富集分析。但是结果&…

排序【七大排序】

文章目录 1. 排序的概念及引用1.1 排序的概念1.2 常见的排序算法 2. 常见排序算法的实现2.1 插入排序2.1.1基本思想&#xff1a;2.1.2 直接插入排序2.1.3 希尔排序( 缩小增量排序 ) 2.2 选择排序2.2.1基本思想&#xff1a;2.2.2 直接选择排序:2.2.3 堆排序 2.3 交换排序2.3.1冒…

uniapp小程序中给web-view页面添加授权弹窗(使用cover-view组件覆盖实现该功能)

效果图&#xff1a; web-view是承载网页的容器。会自动铺满整个小程序页面&#xff0c;个人类型的小程序暂不支持使用。 再看下面一个提示&#xff1a; 每个页面只能有一个 web-view&#xff0c;web-view 会自动铺满整个页面&#xff0c;并覆盖其他组件。 也就是说&#xff0c;…

云安全—云计算基础

0x00 前言 学习云安全&#xff0c;那么必然要对云计算相关的内容进行学习和了解&#xff0c;所以云安全会分为两个部分来进行&#xff0c;首先是云计算先关的内容。 0x01 云计算 广泛传播 云计算最早大范围传播是2006年&#xff0c;8月&#xff0c;在圣何塞【1】举办的SES&a…