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

算法通关村14关 | 堆在数组中找第k大的元素应用

1. 在数组中找第k大元素

题目

LeetCode215:给定整数数组nums和整数k,请返回数组中第k个最大的元素,

思路

解题思路用三个,选择法,堆查找和快速排序。

我们选择用大堆小堆解决问题,“找最大用小堆,找最小用大堆,找中间用两个堆”,我们构造一个大小只有4的小根堆,为了更好的说明情况,我们扩展一下题目序列[3,2,3,1,2,4,5,1,5,6,2,3]。

堆满了之后,只有大于根节点的元素才能入堆,否则就直接抛弃,元素进入堆中,需要调换位置,满足最小堆的结构,如果发现两个子树都小,则应该和最小的元素交换,如果都一样,则随便选一个。

需要注意:堆不满则直接添加;堆满的时候读到大于根节点的元素才将堆顶拿出,放入新读到的数。

代码

我们用的是Javajdk中的PriorityQueue构建最小堆

    /*** 用最小堆在数组中找第k大的元素* @param nums* @param k* @return*/public int findkLargest(int[] nums, int k){if (k > nums.length){return -1;}int len = nums.length;//创建一个含有k个元素的最小堆PriorityQueue<Integer> minHeap = new PriorityQueue<>(k,(a,b) -> (a - b));for (int i = 0; i < k; i++) {minHeap.add(nums[i]);}for (int i = 0; i < len; i++) {Integer topEle = minHeap.peek();//只要比堆顶大的元素,最顶弹出,遍历的元素进去if (nums[i] > topEle){minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.peek();}

相关文章:

算法通关村14关 | 堆在数组中找第k大的元素应用

1. 在数组中找第k大元素 题目 LeetCode215&#xff1a;给定整数数组nums和整数k&#xff0c;请返回数组中第k个最大的元素&#xff0c; 思路 解题思路用三个&#xff0c;选择法&#xff0c;堆查找和快速排序。 我们选择用大堆小堆解决问题&#xff0c;“找最大用小堆&#xff…...

Unity 顶点vertices,uv,与图片贴图,与mesh

mesh就是组成3d物体的三角形们。 mesh由顶点组成的三角形组成&#xff0c;三角形的大小 并不 需要一样&#xff0c;由顶点之间的位置决定。 mesh可以是一个或者多个面。 贴图的原点在左下角&#xff0c;uv是贴图的坐标&#xff0c;数量和顶点数一样&#xff08;不是100%确定…...

Shell编程之函数

目录 基本概念 自定义函数 系统函数 1.read 2.basename 3.dirname 基本概念 将一段代码组合封装在一起实现某个特定的功能或返回某个特定的值&#xff0c;然后给这段代码取个名字&#xff0c;也就是函数名&#xff0c;在需要实现某个特定功能的时候直接调用函数名即可。 函…...

10.物联网LWIP之TCP状态转变

一。TCP状态机 1.青粗线&#xff1a;理想TCP状态转变&#xff08;服务器视角下&#xff09; 2.虚线&#xff1a;被动TCP状态转变&#xff08;服务器视角下&#xff09; 3.细实线&#xff1a;不经常出现的TCP状态转变&#xff08;类似于边界处理&#xff09; 1.青粗线解释--》服…...

Img标签的src地址自动拼接本地域名(localhost:8080)导致图片不显示问题

摘要&#xff1a;做Vueelement ui项目的时候&#xff0c;发现使用element ui的upload上传图片时&#xff0c;不显示的问题。我项目的图片是上传到七牛云&#xff0c;长传成功后返回存储在七牛云中的地址。后面发现是因为返回的地址是外部地址&#xff0c;需要完整的URL&#xf…...

数据结构入门 — 栈

本文属于数据结构专栏文章&#xff0c;适合数据结构入门者学习&#xff0c;涵盖数据结构基础的知识和内容体系&#xff0c;文章在介绍数据结构时会配合上动图演示&#xff0c;方便初学者在学习数据结构时理解和学习&#xff0c;了解数据结构系列专栏点击下方链接。 博客主页&am…...

Unity Android 之 在Unity 中引入 OkHttp的操作注意(OKHttp4.xx- kotlin 的包)简单记录

Unity Android 之 在Unity 中引入 OkHttp的操作注意(OKHttp4.xx- kotlin 的包)简单记录 目录 Unity Android 之 在Unity 中引入 OkHttp的操作注意(OKHttp4.xx- kotlin 的包)简单记录 一、简单介绍 二、OKHttp 4.xx 的 SDK 封装 aar 给 Unity 的使用注意 三、附录 OKHttp 的…...

内嵌功能强大、低功耗STM32WB55CEU7、STM32WB55CGU7 射频微控制器 - MCU, 48-UFQFN

一、概述&#xff1a; STM32WB55xx多协议无线和超低功耗器件内嵌功能强大的超低功耗无线电模块&#xff08;符合蓝牙 低功耗SIG规范5.0和IEEE 802.15.4-2011标准&#xff09;。该器件内含专用的Arm Cortex -M0&#xff0c;用于执行所有的底层实时操作。这些器件基于高性能Arm …...

【测试】笔试03

文章目录 1. 哪种测试模型把测试过程作为需求分析、概要设计、详细设计及编码之后的阶段&#xff08; &#xff09;2. 在下面所列举的逻辑测试覆盖中&#xff0c;测试覆盖最强的是&#xff1f;3. 网络管理员编写了shell程序prog1.sh,测试时程序死循环无法结束,可以通过下列方式…...

JavaScript的while和for循环

一、循环语句 1.认识循环 在开发中我们经常需要做各种各样的循环操作&#xff1a; 比如把一个列表中的商品、歌曲、视频依次输出进行展示&#xff1b;比如对一个列表进行累加计算&#xff1b;比如运行相同的代码将数字 1 到 10 逐个输出&#xff1b; 循环 是一种重复运行同…...

mqtt安卓客户端

1.MQTT&#xff08;消息队列遥测传输协议&#xff09;&#xff0c;是一种基于 发布/订阅 &#xff08;publish/subscribe&#xff09;模式的"轻量级"通讯协议&#xff0c; 该协议构建于TCP/IP协议上 。MQTT最大优点在于&#xff0c;可以以极少的代码和有限的带宽&…...

pdf怎么删除其中一页?

pdf怎么删除其中一页&#xff1f;现在&#xff0c;pdf文件已经深入影响着我们的工作和学习&#xff0c;如果你是一个上班族&#xff0c;那么几乎每天都会使用到pdf格式的电脑文件。当我们阅读一个页数众多的PDF文件时&#xff0c;可能会发现实际上只需要其中的一小部分内容。很…...

10.Redis 渐进式遍历

Redis 渐进式遍历 渐进式遍历scan 渐进式遍历 keys 命令一次性的把整个redis中所有的key都获取到&#xff0c;keys *但这个操作比较危险&#xff0c;可能会一下子得到太多的key,阻塞 redis 服务器。 通过渐进式遍历&#xff0c;就可以做到&#xff0c;既可以获取到所有的 key&…...

字符函数和字符串函数(2)

目录 memcpy memmove memcmp memcpy void * memcpy ( void * destination, const void * source, size_t num ); 1.函数memcpy从source的位置开始向后复制num个字节的数据到destination的内存位置。 2.这个函数在遇到 \0 的时候并不会停下来。 3.如果source和destination有…...

目录扫描+JS文件中提取URL和子域+403状态绕过+指纹识别(dirsearch_bypass403)

dirsearch_bypass403 在安全测试时&#xff0c;安全测试人员信息收集中时可使用它进行目录枚举&#xff0c;目录进行指纹识别&#xff0c;枚举出来的403状态目录可尝试进行绕过&#xff0c;绕过403有可能获取管理员权限。不影响dirsearch原本功能使用 运行流程 dirsearch进行…...

【UE 材质】常用向量运算节点——点积、叉积、归一化

目录 一、点积 二、叉积 三、归一化 一、点积 点积&#xff0c;也称为内积或数量积&#xff0c;是一种用于计算两个向量之间关系的操作。对于两个三维向量 A&#xff08;a1,a2,a3&#xff09;和 B(b1,b2,b3)&#xff0c;它们的点积可以用以下公式表示&#xff1a; ABa1​⋅…...

音视频 ffmpeg命令提取PCM数据

提取PCM ffmpeg -i buweishui.mp3 -ar 48000 -ac 2 -f s16le 48000_2_s16le ffmpeg -i buweishui.mp3 -ar 48000 -ac 2 -sample_fmt s16 out_s16.wav ffmpeg -i buweishui.mp3 -ar 48000 -ac 2 -codec:a pcm_s16le out2_s16le.wav ffmpeg -i buweishui.mp3 -ar 48000 -ac 2 -f…...

【MySQL】实现可扩展性:构建高性能的系统

什么是可扩展性&#xff1f;可扩展性的好处扩展方式纵向扩展&#xff08;Scaling Up&#xff09;横向扩展&#xff08;Scaling Out&#xff09; 总结 &#x1f4af;感谢 &#x1f496; 什么是可扩展性&#xff1f; 可扩展性是指系统能够在需要时轻松地适应更多的工作负载和资源…...

网站用户体验之深度感悟

个性化定制界面和极简版原装界面&#xff0c;哪一个你用起来更加顺手呢&#xff0c;相比之下你更喜欢哪一个&#xff1f; 界面选择&#xff1a; &#xff08;提醒&#xff1a;仅个人感悟。~~&#xff09; 方向一&#xff1a;表明自己的喜好 我个人觉得更喜欢个性化定制界面。…...

目标检测YOLO实战应用案例100讲-道路场景下目标检测与分割模型的压缩研究与实现

目录 前言 目标检测方法 语义分割方法 相关理论基础 2.1 YOLO目标检测算法介绍...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...

flow_controllers

关键点&#xff1a; 流控制器类型&#xff1a; 同步&#xff08;Sync&#xff09;&#xff1a;发布操作会阻塞&#xff0c;直到数据被确认发送。异步&#xff08;Async&#xff09;&#xff1a;发布操作非阻塞&#xff0c;数据发送由后台线程处理。纯同步&#xff08;PureSync…...