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

【力扣】数组中的第K个最大元素

一、题目描述

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

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

题目链接:. - 力扣(LeetCode)

 二、解题思路

1、随机选择基准元素

2、根据基准元素将数组分为三部分:[l, left](该部分小于基准元素key)、[left + 1, right - 1](等于基准元素key)、[right, r](大于基准元素key)。

3、计算每部分所包含的元素个数,分别为a 、b = right - left - 1、 c = r - right + 1;

4、分情况讨论:

三、代码

class Solution {public int findKthLargest(int[] nums, int k) {return qsort(nums, 0, nums.length-1, k);}private int qsort(int[] nums, int l, int r, int k) {if(l == r) {return nums[l];}//随机选择基准元素int key = nums[new Random().nextInt(r-l+1) + l];//根据基准元素将数组划分为三组int left = l-1, right = r+1, i = l;while(i < right) {if(nums[i] < key) {swap(nums, ++left, i++);} else if(nums[i] == key) {i++;} else {swap(nums, --right, i);}}//分情况讨论int b = right - left - 1, c = r - right + 1;if(c >= k) {return qsort(nums, right, r, k);} else if(b + c >= k) {return key;} else {return qsort(nums, l, left, k - b - c);}}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}

 

相关文章:

【力扣】数组中的第K个最大元素

一、题目描述 给定整数数组 nums 和整数 k&#xff0c;请返回数组中第 k 个最大的元素。 请注意&#xff0c;你需要找的是数组排序后的第 k 个最大的元素&#xff0c;而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 输入: [3,2,1,5,…...

WTM的项目中EFCore如何适配人大金仓数据库

一、WTM是什么 WalkingTec.Mvvm框架&#xff08;简称WTM&#xff09;最早开发与2013年&#xff0c;基于Asp.net MVC3 和 最早的Entity Framework, 当初主要是为了解决公司内部开发效率低&#xff0c;代码风格不统一的问题。2017年9月&#xff0c;将代码移植到了.Net Core上&…...

互联网3.0时代的变革者:华贝甄选大模型创新之道

在当今竞争激烈的商业世界中&#xff0c;华贝甄选犹如一颗璀璨的明星&#xff0c;闪耀着独特的光芒。 华贝甄选始终将技术创新与研发视为发展的核心驱动力。拥有先进的研发团队和一流设施&#xff0c;积极探索人工智能、大数据、区块链等前沿技术&#xff0c;为用户提供高性能…...

Tomcat的安全配置

1、生产环境优化 2、部分漏洞修复 转载自风险评估&#xff1a;Tomcat的安全配置&#xff0c;Tomcat安全基线检查加固-CSDN博客...

[笔记] 卷积 - 01 变速箱需要放置多少个加速度传感器?

1.讨论范围 本帖主要对卷积运算的过程和物理意义进行基本的展开&#xff0c;不涉及具体的验算过程。 最终所要达成的目标是&#xff0c;能够自然地判断某种物理现象或者某个测量目标是否与卷积运算有关&#xff0c;以及如何进行测量&#xff0c;搜集数据&#xff0c;调用三方…...

Maya崩溃闪退常见原因及解决方案

Autodesk Maya 是一款功能强大的 3D 计算机图形程序&#xff0c;被电影、游戏和建筑等各个领域的设计师广泛使用。然而&#xff0c;Maya 就像任何其他软件一样可能会发生崩溃问题。在前文中&#xff0c;小编给大家介绍了3ds Max使用V-Ray渲染时的崩溃闪退解决方案&#xff1a; …...

编码与梦想:我的CSDN创作5周年

五年前的今天&#xff0c;我带着对技术的热爱和对知识的渴望&#xff0c;踏上了CSDN的创作之旅。这个平台对于我来说&#xff0c;不仅仅是一个分享和学习的场所&#xff0c;更是我成长和自我实现的见证。 机缘 记得那时&#xff0c;我正为了一个编程难题而苦恼&#xff0c;偶…...

Vue2 基础十Vuex

代码下载 Vuex 概述 组件之间共享数据的方式&#xff1a; 父组件向子组件传值&#xff0c;是以属性的形式绑定值到子组件&#xff08;v-bind&#xff09;&#xff0c;然后子组件用属性props接收。子组件向父组件传值&#xff0c;子组件用 $emit() 自定义事件&#xff0c;父组…...

【大模型】驾驭未知领域:LLM如何处理域外或无意义的提示

驾驭未知领域:LLM如何处理域外或无意义的提示 引言一、概念解析1.1 域外提示1.2 无意义提示二、LLM处理策略2.1 上下文推断2.2 缺省回答2.3 模糊处理2.4 求助于常识三、实例对比3.1 域外提示实例3.2 无意义提示实例四、挑战与局限五、未来展望六、结语附录:术语解释与参考资料…...

Docker容器 为MySQL创建新用户和授权

当您需要为 MySQL 数据库创建一个新用户并配置其访问权限时&#xff0c;可以按照以下步骤操作。我将创建一个名为 newuser 的新用户&#xff0c;并为其授予在任何主机上访问所有数据库的权限。 创建新用户和授权步骤&#xff1a; 登录到 MySQL 服务器 首先&#xff0c;使用具有…...

openssh9.8p1更新 修复漏洞(CVE-2024-6387)

2024 年 7 月&#xff0c;互联网公开披露了一个 OpenSSH 的远程代码执行漏洞&#xff08;CVE-2024-6387&#xff09;。鉴于该漏洞虽然利用较为困难但危害较大&#xff0c;建议所有使用受影响的企业尽快修复该漏洞。 centos7 为例 yum -y install gcc make openssl-devel zlib…...

超市收银系统源码

今天给大家分享一套线上线下打通的收银系统&#xff0c;安卓/win双端线下收银台&#xff0c;可DIY、多模板的三端线上小程序商城&#xff0c;除此之外ERP进销存管理、商品管理、会员营销都很完善。 重点是系统支持OEM贴牌独立部署和全开源源码&#xff0c;非常适合一些正在寻找…...

word 使用手册

word 文档中如何将下行的指定文字退格到上行中 就像是这样的 编号&#xff1a;111 密码&#xff1a;222 编号&#xff1a;123 密码&#xff1a;321 编号&#xff1a;124 密码&#xff1a;331 变成 编号&#xff1a;111密码&#xff1a;222 编号&#xff1a;123密码&#xff1…...

vue学习day03-指令修饰符、v-bind对于样式控制的增强、v-model应用于其他表单元素

7、指令修饰符 &#xff08;1&#xff09;概念&#xff1a; 通过“.”指明一些指令后缀&#xff0c;不同后缀封装了不同的处理操作->简化代码 &#xff08;2&#xff09;按键修饰符 keyup.enter->键盘回车监听 &#xff08;3&#xff09;v-model修饰符 v-model.tri…...

JRE、JVM、JDK分别是什么。

JDK JDK的英文全称是Java Development Kit。JDK是用于制作程序和Java应用程序的软件开发环境。JDK 是 Java 开发工具包&#xff0c;它是 Java 开发者用来编写、编译、调试和运行 Java 程序的集合。JDK 包括了 Java 编译器&#xff08;javac&#xff09;、Java 运行时环境&…...

台灯护眼是真的吗?台灯怎么选对眼睛好?一文带你读懂!

近视问题&#xff0c;这一现代社会的“视力杀手”&#xff0c;正悄然影响着越来越多的人群&#xff0c;尤其是青少年群体。长时间面对电子屏幕和书本&#xff0c;加上不正确的用眼习惯&#xff0c;使得视力下降成为普遍现象。在此背景下&#xff0c;一款优质的护眼台灯显得尤为…...

【学术会议征稿】第五届计算机工程与智能控制学术会议(ICCEIC 2024)

第五届计算机工程与智能控制学术会议&#xff08;ICCEIC 2024) 2024 5th International Conference on Computer Engineering and Intelligent Control 第五届计算机工程与智能控制学术会议&#xff08;ICCEIC 2024&#xff09;将于2024年10月18日至22日在广州举办&#xff0…...

【Golang】slice切片

slice Go语言的切片是对数组的抽象。 数组的使用 package mainimport ("fmt" )// 传递固定长度的数组还是值传递的方式 func printArray(myArray [5]int) {for index, value : range myArray {fmt.Println("index:", index, "value:", value)…...

开源网安模糊测试平台SFuzz全新升级,从标准到实践助力车企安全出海

开源网安模糊测试平台SFuzz全新升级&#xff0c;参照各国相关标准要求进行针对性建设&#xff0c;可为智能网联汽车信息安全测试提供更为强大的工具支持。SFuzz向被测系统输入大量随机数据&#xff0c;模拟各种异常情况&#xff0c;可以发现被测系统内潜在的缺陷和漏洞&#xf…...

Go bytes包

bytes包 Go 语言中的 bytes 包提供了用于操作字节切片的函数集合。字节切片是 Go 语言中非常常用的数据类型&#xff0c;用于表示二进制数据或 UTF-8 编码的字符串。 bytes 包主要功能 操作和处理字节切片搜索和比较字节切片修改和分割字节切片读取和写入字节切片 使用场景 字…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

Linux 下 DMA 内存映射浅析

序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存&#xff0c;但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程&#xff0c;可以参考这篇文章&#xff0c;我觉得写的非常…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

C++中vector类型的介绍和使用

文章目录 一、vector 类型的简介1.1 基本介绍1.2 常见用法示例1.3 常见成员函数简表 二、vector 数据的插入2.1 push_back() —— 在尾部插入一个元素2.2 emplace_back() —— 在尾部“就地”构造对象2.3 insert() —— 在任意位置插入一个或多个元素2.4 emplace() —— 在任意…...

Java设计模式:责任链模式

一、什么是责任链模式&#xff1f; 责任链模式&#xff08;Chain of Responsibility Pattern&#xff09; 是一种 行为型设计模式&#xff0c;它通过将请求沿着一条处理链传递&#xff0c;直到某个对象处理它为止。这种模式的核心思想是 解耦请求的发送者和接收者&#xff0c;…...

Springboot 高校报修与互助平台小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;高校报修与互助平台小程序被用户普遍使用&#xff0c;为…...

OpenHarmony标准系统-HDF框架之I2C驱动开发

文章目录 引言I2C基础知识概念和特性协议&#xff0c;四种信号组合 I2C调试手段硬件软件 HDF框架下的I2C设备驱动案例描述驱动Dispatch驱动读写 总结 引言 I2C基础知识 概念和特性 集成电路总线&#xff0c;由串网12C(1C、12C、Inter-Integrated Circuit BUS)行数据线SDA和串…...

迁移科技3D视觉系统:重塑纸箱拆垛场景的智能革命

一、传统拆垛场景的困局与破局之道 在汽车零部件仓库中&#xff0c;每天有超过2万只异形纸箱需要拆垛分拣。传统人工拆垛面临三大挑战&#xff1a; 效率瓶颈&#xff1a;工人每小时仅能处理200-300件&#xff0c;且存在间歇性疲劳安全隐患&#xff1a;20kg以上重箱搬运导致年…...

【大厂机试题+算法可视化】最长的指定瑕疵度的元音子串

题目 开头和结尾都是元音字母&#xff08;aeiouAEIOU&#xff09;的字符串为元音字符串&#xff0c;其中混杂的非元音字母数量为其瑕疵度。比如: “a” 、 “aa”是元音字符串&#xff0c;其瑕疵度都为0 “aiur”不是元音字符串&#xff08;结尾不是元音字符&#xff09; “…...