leetcode hot100【LeetCode 215.数组中的第K个最大元素】java实现
LeetCode 215.数组中的第K个最大元素
题目描述
给定一个整数数组 nums 和一个整数 k,请返回数组中第 k 个最大的元素。
请注意,要求排名是从大到小的,因此第 k 个最大元素是排序后的第 k 个元素。你需要设计一个高效的算法来解决这个问题。
示例 1:
输入:nums = [3,2,1,5,6,4], k = 2
输出:5
解释:数组中第二大的元素是 5。
示例 2:
输入:nums = [3,2,3,1,2,4,5,5,6], k = 4
输出:4
解释:数组中第四大的元素是 4。
Java 实现代码
class Solution {public int findKthLargest(int[] nums, int k) {// 使用最小堆来找第k大的元素PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);for (int num : nums) {minHeap.offer(num);if (minHeap.size() > k) {minHeap.poll(); // 维护堆的大小为k,去除堆中最小的元素}}return minHeap.peek(); // 最小堆的根就是第k大的元素}
}
解题思路
最小堆方法: 我们可以利用最小堆(
PriorityQueue)来实现。堆是一个完全二叉树,可以在O(logn)时间内进行插入和删除操作。
- 将数组中的前
k个元素插入到最小堆中。- 如果当前堆中元素个数大于k,则吐出。
- 最后,堆顶的元素就是第
k大的元素。这种方法的时间复杂度是
O(n log k),其中n是数组的大小,k是需要找到的第k大元素。快速选择法: 另一种方法是使用快速排序的思想,即快速选择(Quickselect)。通过对数组进行划分,选择性地进入有可能包含第
k
大元素的子数组。这个方法的平均时间复杂度是O(n)。
复杂度分析
- 时间复杂度: 使用最小堆方法时,插入一个元素的时间复杂度是
O(log k),所以对于数组中n个元素,总的时间复杂度是O(n log k)。- 空间复杂度:
O(k),因为堆中最多存储k个元素。
举例说明执行过程
假设有数组
nums = [3,2,1,5,6,4],我们要求第2大的元素。
- 初始数组:
[3,2,1,5,6,4],k = 2- 创建一个大小为
2的最小堆:
- 插入
3,堆为[3]- 插入
2,堆为[2, 3](因为堆是最小堆,所以自动调整)- 插入
1,堆为[1, 3](删除最小元素2)- 插入
5,堆为[3, 5](删除最小元素1)- 插入
6,堆为[5, 6](删除最小元素3)- 插入
4,堆为[5, 6](删除最小元素4)- 最终堆中元素为
[5, 6],堆顶为5,即第2大元素。
相关文章:
leetcode hot100【LeetCode 215.数组中的第K个最大元素】java实现
LeetCode 215.数组中的第K个最大元素 题目描述 给定一个整数数组 nums 和一个整数 k,请返回数组中第 k 个最大的元素。 请注意,要求排名是从大到小的,因此第 k 个最大元素是排序后的第 k 个元素。你需要设计一个高效的算法来解决这个问题。…...
簡單易懂:如何在Windows系統中修改IP地址?
無論是為了連接到一個新的網路,還是為了解決網路連接問題,修改IP地址都是一個常見的操作。本文將詳細介紹如何在Windows系統中修改IP地址,包括靜態IP地址的設置和動態IP地址的獲取。 IP地址是什麼? IP地址是互聯網協議地址的簡稱…...
Python中的23种设计模式:详细分类与总结
设计模式是解决特定问题的通用方法,分为创建型模式、结构型模式和行为型模式三大类。以下是对每种模式的详细介绍,包括其核心思想、应用场景和优缺点。 一、创建型模式(Creational Patterns) 创建型模式关注对象的创建࿰…...
日历使用及汉化——fullcalendar前端
官网 FullCalendar - JavaScript Event Calendar 引入项目 <link hrefhttps://cdnjs.cloudflare.com/ajax/libs/fullcalendar/5.10.1/main.min.css relstylesheet /><script srchttps://cdnjs.cloudflare.com/ajax/libs/fullcalendar/5.10.1/main.min.js></sc…...
视频截断,使用 FFmpeg
使用 FFmpeg 截取视频并去掉 5 分 49 秒后的内容,可以使用以下命令: ffmpeg -i input.mp4 -t 00:05:49 -c:v libx264 -crf 23 -preset medium -c:a aac -b:a 192k output.mp4-i input.mp4: 指定输入视频文件 input.mp4。 -t 00:05:49&#x…...
使用系统内NCCL环境重新编译Pytorch
intro: 费了老大劲,来重新编译pytorch,中间报了无数错误。原生的编译好的pytorch是直接用的其自带NCCL库,并且从外部是不能进行插桩的,因为根本找不到libnccl.so文件。下面记录下重新编译pytorch的过程。指定USE_SYSTEM_NCCL1。这…...
1. Klipper从安装到运行
本文记录Klipper固件从安装,配置到运行的详细过程 Klipper是3D打印机固件之一,它通常运行在linux系统(常使用Debian,其它的linux版本也可以)上,因此需要一个能运行Linux系统的硬件,比如电脑&am…...
docker 卸载与安装
卸载 查询之前安装的docker, 没有查到则不用卸载删除 yum list installed | grep docker 卸载安装包 yum remove docker-* -y 删除镜像、容器、默认挂载卷 rm -rf /var/lib/docker 安装 -ce 安装稳定版本 -y 当安装过程提示选择全部为 "yes" yum install d…...
跨部门文件共享安全:平衡协作与风险的关键策略
在现代企业中,跨部门协作已成为推动业务发展的关键因素。然而,随着信息的自由流动和共享,文件安全风险也随之增加。如何在促进跨部门协作的同时,确保文件共享的安全性,成为了一个亟待解决的问题。 一、明确文件分类与…...
基于单片机的智慧小区人脸识别门禁系统
本设计基于单片机的智慧小区人脸识别门禁系统。由STM32F103C8T6单片机核心板、显示模块、摄像头模块、舵机模块、按键模块和电源模块组成。可以通过摄像头模块对进入人员人脸数据进行采集,识别成功后,舵机模块动作,模拟门禁打开,门…...
【es6】原生js在页面上画矩形及删除的实现方法
画一个矩形,可以选中高亮,删除自己效果的实现,后期会丰富下细节,拖动及拖动调整矩形大小 实现效果 代码实现 class Draw {constructor() {this.x 0this.y 0this.disX 0this.disY 0this.startX 0this.startY 0this.mouseDo…...
【git实践】分享一个适用于敏捷开发的分支管理策略
文章目录 1. 背景2. 分支管理实践2.1. 敏捷开发中分支管理面临的问题2.2. 分支管理策略2.3. 还需要注意的一些问题 3.总结 1. 背景 在实际的开发工作中,我们往往会面临多任务并行研发,多个环境管理的情况,这种情况下,一个合适的分…...
Redis与MySQL如何保证数据一致性
Redis与MySQL如何保证数据一致性 简单来说 该场景主要发生在读写并发进行时,才会发生数据不一致。 主要流程就是要么先操作缓存,要么先操作Redis,操作也分修改和删除。 一般修改要执行一系列业务代码,所以一般直接删除成本较低…...
基于微信小程序的教室预约系统+LW示例参考
1.项目介绍 功能模块:管理员(学生管理、教师管理、申请管理、设备管理、报修管理等)、普通用户/学生(注册登录、申请预约、退订、报修等)技术选型:SSM、JSP、uniapp等测试环境:idea2024&#x…...
Linux 安装 Git 服务器
一、安装 Git 1. 在 CentOS/RHEL 中使用以下命令: sudo yum update -y # 或者 sudo dnf update -y (在较新的系统中) sudo yum install git -y验证安装:git --version 2. 配置 Git 用户 git config --global user.name "Your Name" git co…...
总结:Yarn资源管理
一、介绍 本文梳理下Yarn的资源分配计算逻辑。 二、配置 - 资源限制 1、配置NodeManager可分配的资源池的总量 <property><name>yarn.nodemanager.resource.memory-mb</name><value>4096</value> </property> 作用对象:节点管理器(No…...
Python学习34天
import random class Game: peo0 rob0 # # def __init__(self,peo,rob): # self.peopeo # self.robrob def Play(self): """ 石头剪刀布游戏,0代表石头,1代见到,2代表石头 …...
深入浅出 WebSocket:构建实时数据大屏的高级实践
简介 请参考下方,学习入门操作 基于 Flask 和 Socket.IO 的 WebSocket 实时数据更新实现 在当今数字化时代,实时性是衡量互联网应用的重要指标之一。无论是股票交易、在线游戏,还是实时监控大屏,WebSocket 已成为实现高效、双向…...
三开关VUE组件
一、使用效果 <template><QqThreeSwitch v-model"value" /><!-- <SqThreeSwitch v-model"value" :options"[test1, test2, test3]"><template #left-action><div style"display: flex"><IconMoon…...
SpringCloud+SpringCloudAlibaba学习笔记
SpringCloud 服务注册中心 eureka ap 高可用 分布式容错 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-netflix-eureka-server</artifactId> </dependency> <dependency><groupId…...
SpringBoot生产级监控与异常日志运维实战,线上项目稳定排查不慌
SpringBoot项目本地开发调试正常,部署到生产环境后频繁出现接口报错、服务卡顿、内存溢出、接口响应缓慢、数据库连接耗尽等线上问题,开发者无法实时查看项目运行状态,报错无精准日志定位,排查问题耗时费力,严重影响业…...
手把手教你用PyTorch复现EfficientNetV2(附完整代码):从网络搭建到渐进式训练全流程
从零实现EfficientNetV2:代码级解析与渐进式训练实战 当你第一次翻开EfficientNetV2论文时,那些复杂的复合缩放系数和渐进式训练策略可能让人望而生畏。但别担心——本文将带你用PyTorch从最基础的卷积模块开始,逐层构建这个高效的视觉模型。…...
跨设备代码同步工具cursor-sync:设计原理与工程实践指南
1. 项目概述:一个为开发者设计的代码同步工具如果你和我一样,经常在多个设备上切换着写代码——比如在公司用台式机,回家用笔记本,甚至偶尔在平板上改几行——那你一定对“代码同步”这个痛点深有体会。手动复制粘贴、用U盘倒腾、…...
基于硬件虚拟化的AI智能体安全隔离方案Clawcage设计与实现
1. 项目概述:为AI智能体打造一个坚不可摧的“笼子”如果你最近在尝试运行一些本地的AI智能体,比如Claude Desktop、Cursor的Agent模式,或者各种开源的AI助手工具,心里可能总会有点打鼓。这些工具功能强大,但它们背后运…...
从新手到老手:四类Ozon卖家选品工具选择指南
选品工具没有“最好”,只有“最匹配你当前阶段”。四类卖家,四种方案。市面上的Ozon选品工具,功能各有侧重。有的擅长给数据,有的擅长给结论,有的擅长管店铺。不同阶段的卖家,痛点不同,适合的工…...
从CANoe实战出发:深度解析UDS网络层诊断中的流控帧(FC)与时间参数STmin
从CANoe实战解析UDS流控帧:FC与STmin参数调优指南 在汽车电子测试领域,UDS诊断协议的网络层流控机制直接影响着ECU通信的可靠性与效率。当测试工程师在CANoe环境中模拟诊断会话时,经常会遇到因流控帧参数配置不当导致的报文丢失、响应超时等问…...
构建个人技能库:高效沉淀与复用代码片段的工程实践
1. 项目概述:一个技能库的诞生与价值最近在整理自己的技术工具箱时,我意识到一个问题:很多实用的代码片段、脚本和解决方案,都散落在不同的项目、笔记甚至聊天记录里。当需要快速解决一个特定问题时,要么得花时间回忆&…...
Neovim集成ChatGPT:AI编程助手插件配置与实战指南
1. 项目概述:当Neovim遇上ChatGPT,一个插件如何重塑你的编码体验 如果你是一个Neovim的深度用户,同时又对AI辅助编程抱有极大的热情,那么你很可能已经听说过或者正在寻找一个完美的结合点。 jackMort/ChatGPT.nvim 这个项目&…...
霍尔效应绝对式双码道磁编码器【附电路】
✨ 长期致力于双码道多磁极编码器、硬件设计、误差仿真与校正、算法设计与优化研究工作,擅长数据搜集与处理、建模仿真、程序编写、仿真设计。 ✅ 专业定制毕设、代码 ✅ 如需沟通交流,点击《获取方式》 (1)双码道多磁极磁场检测硬…...
5分钟快速上手:qmcdump免费解密QQ音乐文件的终极指南
5分钟快速上手:qmcdump免费解密QQ音乐文件的终极指南 【免费下载链接】qmcdump 一个简单的QQ音乐解码(qmcflac/qmc0/qmc3 转 flac/mp3),仅为个人学习参考用。 项目地址: https://gitcode.com/gh_mirrors/qm/qmcdump 你是否…...
