【力扣】数组中的第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,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 输入: [3,2,1,5,…...
WTM的项目中EFCore如何适配人大金仓数据库
一、WTM是什么 WalkingTec.Mvvm框架(简称WTM)最早开发与2013年,基于Asp.net MVC3 和 最早的Entity Framework, 当初主要是为了解决公司内部开发效率低,代码风格不统一的问题。2017年9月,将代码移植到了.Net Core上&…...
互联网3.0时代的变革者:华贝甄选大模型创新之道
在当今竞争激烈的商业世界中,华贝甄选犹如一颗璀璨的明星,闪耀着独特的光芒。 华贝甄选始终将技术创新与研发视为发展的核心驱动力。拥有先进的研发团队和一流设施,积极探索人工智能、大数据、区块链等前沿技术,为用户提供高性能…...
Tomcat的安全配置
1、生产环境优化 2、部分漏洞修复 转载自风险评估:Tomcat的安全配置,Tomcat安全基线检查加固-CSDN博客...
[笔记] 卷积 - 01 变速箱需要放置多少个加速度传感器?
1.讨论范围 本帖主要对卷积运算的过程和物理意义进行基本的展开,不涉及具体的验算过程。 最终所要达成的目标是,能够自然地判断某种物理现象或者某个测量目标是否与卷积运算有关,以及如何进行测量,搜集数据,调用三方…...
Maya崩溃闪退常见原因及解决方案
Autodesk Maya 是一款功能强大的 3D 计算机图形程序,被电影、游戏和建筑等各个领域的设计师广泛使用。然而,Maya 就像任何其他软件一样可能会发生崩溃问题。在前文中,小编给大家介绍了3ds Max使用V-Ray渲染时的崩溃闪退解决方案: …...
编码与梦想:我的CSDN创作5周年
五年前的今天,我带着对技术的热爱和对知识的渴望,踏上了CSDN的创作之旅。这个平台对于我来说,不仅仅是一个分享和学习的场所,更是我成长和自我实现的见证。 机缘 记得那时,我正为了一个编程难题而苦恼,偶…...
Vue2 基础十Vuex
代码下载 Vuex 概述 组件之间共享数据的方式: 父组件向子组件传值,是以属性的形式绑定值到子组件(v-bind),然后子组件用属性props接收。子组件向父组件传值,子组件用 $emit() 自定义事件,父组…...
【大模型】驾驭未知领域:LLM如何处理域外或无意义的提示
驾驭未知领域:LLM如何处理域外或无意义的提示 引言一、概念解析1.1 域外提示1.2 无意义提示二、LLM处理策略2.1 上下文推断2.2 缺省回答2.3 模糊处理2.4 求助于常识三、实例对比3.1 域外提示实例3.2 无意义提示实例四、挑战与局限五、未来展望六、结语附录:术语解释与参考资料…...
Docker容器 为MySQL创建新用户和授权
当您需要为 MySQL 数据库创建一个新用户并配置其访问权限时,可以按照以下步骤操作。我将创建一个名为 newuser 的新用户,并为其授予在任何主机上访问所有数据库的权限。 创建新用户和授权步骤: 登录到 MySQL 服务器 首先,使用具有…...
openssh9.8p1更新 修复漏洞(CVE-2024-6387)
2024 年 7 月,互联网公开披露了一个 OpenSSH 的远程代码执行漏洞(CVE-2024-6387)。鉴于该漏洞虽然利用较为困难但危害较大,建议所有使用受影响的企业尽快修复该漏洞。 centos7 为例 yum -y install gcc make openssl-devel zlib…...
超市收银系统源码
今天给大家分享一套线上线下打通的收银系统,安卓/win双端线下收银台,可DIY、多模板的三端线上小程序商城,除此之外ERP进销存管理、商品管理、会员营销都很完善。 重点是系统支持OEM贴牌独立部署和全开源源码,非常适合一些正在寻找…...
word 使用手册
word 文档中如何将下行的指定文字退格到上行中 就像是这样的 编号:111 密码:222 编号:123 密码:321 编号:124 密码:331 变成 编号:111密码:222 编号:123密码࿱…...
vue学习day03-指令修饰符、v-bind对于样式控制的增强、v-model应用于其他表单元素
7、指令修饰符 (1)概念: 通过“.”指明一些指令后缀,不同后缀封装了不同的处理操作->简化代码 (2)按键修饰符 keyup.enter->键盘回车监听 (3)v-model修饰符 v-model.tri…...
JRE、JVM、JDK分别是什么。
JDK JDK的英文全称是Java Development Kit。JDK是用于制作程序和Java应用程序的软件开发环境。JDK 是 Java 开发工具包,它是 Java 开发者用来编写、编译、调试和运行 Java 程序的集合。JDK 包括了 Java 编译器(javac)、Java 运行时环境&…...
台灯护眼是真的吗?台灯怎么选对眼睛好?一文带你读懂!
近视问题,这一现代社会的“视力杀手”,正悄然影响着越来越多的人群,尤其是青少年群体。长时间面对电子屏幕和书本,加上不正确的用眼习惯,使得视力下降成为普遍现象。在此背景下,一款优质的护眼台灯显得尤为…...
【学术会议征稿】第五届计算机工程与智能控制学术会议(ICCEIC 2024)
第五届计算机工程与智能控制学术会议(ICCEIC 2024) 2024 5th International Conference on Computer Engineering and Intelligent Control 第五届计算机工程与智能控制学术会议(ICCEIC 2024)将于2024年10月18日至22日在广州举办࿰…...
【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全新升级,参照各国相关标准要求进行针对性建设,可为智能网联汽车信息安全测试提供更为强大的工具支持。SFuzz向被测系统输入大量随机数据,模拟各种异常情况,可以发现被测系统内潜在的缺陷和漏洞…...
Go bytes包
bytes包 Go 语言中的 bytes 包提供了用于操作字节切片的函数集合。字节切片是 Go 语言中非常常用的数据类型,用于表示二进制数据或 UTF-8 编码的字符串。 bytes 包主要功能 操作和处理字节切片搜索和比较字节切片修改和分割字节切片读取和写入字节切片 使用场景 字…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
WEB3全栈开发——面试专业技能点P4数据库
一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库,基于 mysql 库改进而来,具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点: 支持 Promise / async-await…...
【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架
文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理:检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目:RankRAG:Unifying Context Ranking…...
