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

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大的元素}
}

解题思路

  1. 最小堆方法: 我们可以利用最小堆(PriorityQueue)来实现。堆是一个完全二叉树,可以在 O(logn) 时间内进行插入和删除操作。

    • 将数组中的前 k 个元素插入到最小堆中。
    • 如果当前堆中元素个数大于k,则吐出。
    • 最后,堆顶的元素就是第 k 大的元素。

    这种方法的时间复杂度是 O(n log k),其中 n 是数组的大小,k 是需要找到的第 k 大元素。

  2. 快速选择法: 另一种方法是使用快速排序的思想,即快速选择(Quickselect)。通过对数组进行划分,选择性地进入有可能包含第 k
    大元素的子数组。这个方法的平均时间复杂度是 O(n)

复杂度分析

  • 时间复杂度: 使用最小堆方法时,插入一个元素的时间复杂度是 O(log k),所以对于数组中 n 个元素,总的时间复杂度是 O(n log k)
  • 空间复杂度: O(k),因为堆中最多存储 k 个元素。

举例说明执行过程

假设有数组 nums = [3,2,1,5,6,4],我们要求第 2 大的元素。

  1. 初始数组:[3,2,1,5,6,4]k = 2
  2. 创建一个大小为 2 的最小堆:
    • 插入 3,堆为 [3]
    • 插入 2,堆为 [2, 3](因为堆是最小堆,所以自动调整)
    • 插入 1,堆为 [1, 3](删除最小元素 2
    • 插入 5,堆为 [3, 5](删除最小元素 1
    • 插入 6,堆为 [5, 6](删除最小元素 3
    • 插入 4,堆为 [5, 6](删除最小元素 4
  3. 最终堆中元素为 [5, 6],堆顶为 5,即第 2 大元素。

相关文章:

leetcode hot100【LeetCode 215.数组中的第K个最大元素】java实现

LeetCode 215.数组中的第K个最大元素 题目描述 给定一个整数数组 nums 和一个整数 k&#xff0c;请返回数组中第 k 个最大的元素。 请注意&#xff0c;要求排名是从大到小的&#xff0c;因此第 k 个最大元素是排序后的第 k 个元素。你需要设计一个高效的算法来解决这个问题。…...

簡單易懂:如何在Windows系統中修改IP地址?

無論是為了連接到一個新的網路&#xff0c;還是為了解決網路連接問題&#xff0c;修改IP地址都是一個常見的操作。本文將詳細介紹如何在Windows系統中修改IP地址&#xff0c;包括靜態IP地址的設置和動態IP地址的獲取。 IP地址是什麼&#xff1f; IP地址是互聯網協議地址的簡稱…...

Python中的23种设计模式:详细分类与总结

设计模式是解决特定问题的通用方法&#xff0c;分为创建型模式、结构型模式和行为型模式三大类。以下是对每种模式的详细介绍&#xff0c;包括其核心思想、应用场景和优缺点。 一、创建型模式&#xff08;Creational Patterns&#xff09; 创建型模式关注对象的创建&#xff0…...

日历使用及汉化——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 秒后的内容&#xff0c;可以使用以下命令&#xff1a; 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&#xff1a; 指定输入视频文件 input.mp4。 -t 00:05:49&#x…...

使用系统内NCCL环境重新编译Pytorch

intro&#xff1a; 费了老大劲,来重新编译pytorch&#xff0c;中间报了无数错误。原生的编译好的pytorch是直接用的其自带NCCL库&#xff0c;并且从外部是不能进行插桩的&#xff0c;因为根本找不到libnccl.so文件。下面记录下重新编译pytorch的过程。指定USE_SYSTEM_NCCL1。这…...

1. Klipper从安装到运行

本文记录Klipper固件从安装&#xff0c;配置到运行的详细过程 Klipper是3D打印机固件之一&#xff0c;它通常运行在linux系统&#xff08;常使用Debian&#xff0c;其它的linux版本也可以&#xff09;上&#xff0c;因此需要一个能运行Linux系统的硬件&#xff0c;比如电脑&am…...

docker 卸载与安装

卸载 查询之前安装的docker, 没有查到则不用卸载删除 yum list installed | grep docker 卸载安装包 yum remove docker-* -y 删除镜像、容器、默认挂载卷 rm -rf /var/lib/docker 安装 -ce 安装稳定版本 -y 当安装过程提示选择全部为 "yes" yum install d…...

跨部门文件共享安全:平衡协作与风险的关键策略

在现代企业中&#xff0c;跨部门协作已成为推动业务发展的关键因素。然而&#xff0c;随着信息的自由流动和共享&#xff0c;文件安全风险也随之增加。如何在促进跨部门协作的同时&#xff0c;确保文件共享的安全性&#xff0c;成为了一个亟待解决的问题。 一、明确文件分类与…...

基于单片机的智慧小区人脸识别门禁系统

本设计基于单片机的智慧小区人脸识别门禁系统。由STM32F103C8T6单片机核心板、显示模块、摄像头模块、舵机模块、按键模块和电源模块组成。可以通过摄像头模块对进入人员人脸数据进行采集&#xff0c;识别成功后&#xff0c;舵机模块动作&#xff0c;模拟门禁打开&#xff0c;门…...

【es6】原生js在页面上画矩形及删除的实现方法

画一个矩形&#xff0c;可以选中高亮&#xff0c;删除自己效果的实现&#xff0c;后期会丰富下细节&#xff0c;拖动及拖动调整矩形大小 实现效果 代码实现 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. 背景 在实际的开发工作中&#xff0c;我们往往会面临多任务并行研发&#xff0c;多个环境管理的情况&#xff0c;这种情况下&#xff0c;一个合适的分…...

Redis与MySQL如何保证数据一致性

Redis与MySQL如何保证数据一致性 简单来说 该场景主要发生在读写并发进行时&#xff0c;才会发生数据不一致。 主要流程就是要么先操作缓存&#xff0c;要么先操作Redis&#xff0c;操作也分修改和删除。 一般修改要执行一系列业务代码&#xff0c;所以一般直接删除成本较低…...

基于微信小程序的教室预约系统+LW示例参考

1.项目介绍 功能模块&#xff1a;管理员&#xff08;学生管理、教师管理、申请管理、设备管理、报修管理等&#xff09;、普通用户/学生&#xff08;注册登录、申请预约、退订、报修等&#xff09;技术选型&#xff1a;SSM、JSP、uniapp等测试环境&#xff1a;idea2024&#x…...

Linux 安装 Git 服务器

一、安装 Git 1. 在 CentOS/RHEL 中使用以下命令&#xff1a; sudo yum update -y # 或者 sudo dnf update -y (在较新的系统中) sudo yum install git -y验证安装&#xff1a;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): """ 石头剪刀布游戏&#xff0c;0代表石头&#xff0c;1代见到&#xff0c;2代表石头 …...

深入浅出 WebSocket:构建实时数据大屏的高级实践

简介 请参考下方&#xff0c;学习入门操作 基于 Flask 和 Socket.IO 的 WebSocket 实时数据更新实现 在当今数字化时代&#xff0c;实时性是衡量互联网应用的重要指标之一。无论是股票交易、在线游戏&#xff0c;还是实时监控大屏&#xff0c;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…...

开源AI投资情报工具MacroClaw:从数据抓取到智能分析的完整实践

1. 项目概述&#xff1a;一个实时投资情报的AI智能体如果你和我一样&#xff0c;每天需要花大量时间在财经新闻、大宗商品价格和地缘政治动态上&#xff0c;试图从海量信息中提炼出对投资决策有用的信号&#xff0c;那你一定明白这有多耗时耗力。传统的资讯平台要么信息滞后&am…...

加拿大无人机产业:从感知到执行的自主化跃迁与BVLOS破局

1. 加拿大无人机产业的现状与挑战提起无人机&#xff0c;很多人脑海里首先蹦出来的可能是大疆&#xff0c;那个在全球消费级和部分商用市场占据绝对主导地位的中国品牌。这确实是一个不争的事实&#xff0c;也是加拿大本土无人机产业必须直面的现实。我接触过不少加拿大的初创公…...

自动化测试(十) 微服务测试策略-单元到集成到契约到端到端分层实战

微服务测试策略&#xff1a;单元→集成→契约→端到端分层实战前面咱们分别聊了单元测试、接口测试、契约测试。今天把它们串起来&#xff0c;聊聊微服务架构下怎么设计完整的测试策略——每一层测什么、怎么测、用什么工具。一、微服务测试的"金字塔"变体 单体应用的…...

数据结构实战:用C语言链表手搓多项式加法,附赠PTA 6-3题全测试点解析

数据结构实战&#xff1a;用C语言链表手搓多项式加法&#xff0c;附赠PTA 6-3题全测试点解析 链表操作是数据结构课程的核心技能之一&#xff0c;而多项式加法则是检验这项能力的经典考题。无论是PTA、PAT还是LeetCode&#xff0c;这类题目都频繁出现。本文将带你从零开始&…...

RAG 系统优化全流程:从数据入库到召回排序

RAG(Retrieval-Augmented Generation)系统的检索质量直接决定生成内容的上限。本文从工程落地角度,系统梳理 RAG 检索链路的三个核心阶段——入库、查询与召回。针对每个阶段的关键技术(语义分割、问答模拟、查询改写、语义校验、混合检索、语义重排)给出定义、问题背景、…...

阴阳师自动化脚本终极指南:如何用OnmyojiAutoScript一键托管你的日常游戏

阴阳师自动化脚本终极指南&#xff1a;如何用OnmyojiAutoScript一键托管你的日常游戏 【免费下载链接】OnmyojiAutoScript Onmyoji Auto Script | 阴阳师脚本 项目地址: https://gitcode.com/gh_mirrors/on/OnmyojiAutoScript 还在为阴阳师繁琐的日常任务而烦恼吗&#…...

英特尔无人机芯片战略:从RealSense到异构计算的技术博弈与市场挑战

1. 从移动梦碎到天空野心&#xff1a;英特尔为何押注无人机芯片&#xff1f;2016年5月&#xff0c;当英特尔在加州棕榈泉的夜空中点亮100架编队飞行的无人机时&#xff0c;这场名为“Drone 100”的灯光秀&#xff0c;其意义远不止一场炫目的营销。它更像是一份宣言&#xff0c;…...

Turms开发者定制指南:如何基于源码进行二次开发

Turms开发者定制指南&#xff1a;如何基于源码进行二次开发 【免费下载链接】turms &#x1f54a;️ The worlds most advanced open source instant messaging engine for 100K~10M concurrent users https://turms-im.github.io/docs 项目地址: https://gitcode.com/gh_mir…...

嵌入式产品如何通过RTOS选型抢占市场先机

1. 项目概述&#xff1a;为什么“上市时机”是嵌入式产品的生死线在嵌入式系统开发这个行当里摸爬滚打了十几年&#xff0c;我见过太多团队把“功能实现”和“性能达标”作为项目的终极目标&#xff0c;却在一个更根本的问题上栽了跟头&#xff1a;上市时机。你可能觉得&#x…...

taotoken模型广场功能体验与主流模型选型建议

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 taotoken模型广场功能体验与主流模型选型建议 1. 平台入口与模型广场概览 登录Taotoken控制台后&#xff0c;最直观的功能入口之一…...