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

【LeetCode】215.数组中的第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 <= 10^5
  • -10^4 <= nums[i] <= 10^4

解答

源代码

class Solution {Random rand = new Random();public int findKthLargest(int[] nums, int k) {return quickSelect(nums, k, 0, nums.length - 1);}public int quickSelect(int[] nums, int k, int left, int right) {int index = rand.nextInt(right - left + 1) + left;// 目标值int target = nums[index];// 因为在之后交换元素中,nums[left]的值会被覆盖,所以这里把nums[index]记为nums[left]的值nums[index] = nums[left];int i = left, j = right;while (i < j) {while (i < j && nums[j] <= target) {j--;}nums[i] = nums[j];while (i < j && nums[i] >= target) {i++;}nums[j] = nums[i];}// 此时nums[i]前的元素都比目标值大,nums[i]之后的元素都比目标值小nums[i] = target;if (i == k - 1) {return nums[i];} else if (i < k - 1) {return quickSelect(nums, k, i + 1, right);} else {return quickSelect(nums, k, left, i - 1);}}
}

总结

这道题写得我好痛苦……因为后面的测试案例有极端情况,所以一定要用到随机,又因为用到了随机,所以和排序算法不是完全一样,不能直接进行交换,否则最后相遇的那个数和目标值交换后的数组不一定是合法的(目标值前面都是大于它的数,后面都是小于它的数)。

相关文章:

【LeetCode】215.数组中的第K个最大元素

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

MySQL学习记录:第七章 存储过程和函数

文章目录 第七章 存储过程和函数一、存储过程1、 创建语法*2、调用语法(1)空参列表(2)创建带in参数模式的存储过程,需终端运行(3)创建带out参数模式的存储过程,需终端运行(4)创建带inout参数模式的存储过程,需终端运行3、删除存储过程4、查看存储过程的信息二、函数…...

Docker中gitlab以及gitlab-runner的安装与使用

1、本文主要讲述如何使用Docker安装gitlab以及gitlab-runner&#xff0c;并且会讲述gitlab-runner如何使用 2、gitlab部分不需要修改过多的配置即可使用&#xff0c;本文未讲述https配置&#xff0c;如有需求&#xff0c;可自行百度 3、Docker如何安装可以自行百度 一、Docker安…...

一起学SF框架系列5.12-spring-beans-数据绑定dataBinding

数据绑定有助于将用户输入动态绑定到应用程序的域模型&#xff08;或用于处理用户输入的任何对象&#xff09;&#xff0c;主要用于web层&#xff0c;但实际可用于任何层。Spring提供了DataBinder来做到这一点&#xff0c;并提供了Validator进行数据验证&#xff0c;两者组成了…...

火热报名中 | 赛宁独家技术支持第七届“蓝帽杯”网络安全技能大赛

由公安部网络安全保卫局、教育部教育管理信息中心、中国教育协会指导&#xff0c;中国人民公安大学主办&#xff0c;奇安信科技集团股份有限公司协办&#xff0c;南京赛宁信息技术有限公司提供技术支持的2023第七届“蓝帽杯”全国大学生网络安全技能大赛于近日正式开启报名。 …...

无涯教程-jQuery - Ajax Tutorial函数

AJAX是用于创建交互式Web应用程序的Web开发技术。如果您了解JavaScript,HTML,CSS和XML,则只需花费一个小时即可开始使用AJAX。 为什么要学习Ajax? AJAX代表 A 同步 Ja vaScript和 X ML。 AJAX是一项新技术,可借助XML,HTML,CSS和Java Script创建更好,更快,更具交互性的Web应用…...

Android日志

Android中的日志工具类是Log&#xff08;android.util.Log&#xff09;&#xff0c;这个类中提供了如下5个方法来供我们打印日志。 Log.v()。用于打印那些最为琐碎的、意义最小的日志信息。对应级别verbose&#xff0c;是Android日志里面级别最低的一种。 Log.d()。用于打印一…...

【Golang 接口自动化08】使用标准库httptest完成HTTP请求的Mock测试

目录 前言 http包的HandleFunc函数 http.Request/http.ResponseWriter httptest 定义被测接口 测试代码 测试执行 总结 资料获取方法 前言 Mock是一个做自动化测试永远绕不过去的话题。本文主要介绍使用标准库net/http/httptest完成HTTP请求的Mock的测试方法。 可能有…...

SpringBoot自定义注解 + AOP+分布式Redis 防止重复提交

第一步 引入依赖pom.xml&#xff1a; <dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.16.3</version> <!-- 使用最新版本 --></dependency><dependency><groupId&g…...

3.yum安装分布式LNMP--剧本

文章目录 修改hosts创建剧本文件 修改hosts vim /etc/ansible/hosts[webservers] 192.168.242.67[dbservers] 192.168.242.68[phpservers] 192.168.242.69创建剧本文件 vim lnmp.yaml- name: nginx playhosts: webserversremote_user: rootvars:- http_port: 192.168.242.67:…...

论文笔记:Fine-Grained Urban Flow Prediction

2021 WWW 1 intro 细粒度城市流量预测 两个挑战 细粒度数据中观察到的网格间的转移动态使得预测变得更加复杂 需要在全局范围内捕获网格单元之间的空间依赖性单独学习外部因素&#xff08;例如天气、POI、路段信息等&#xff09;对大量网格单元的影响非常具有挑战性——>论…...

系统集成|第八章(笔记)

目录 第八章 进度管理8.1 主要过程8.1.1 规划进度管理8.1.2 定义活动8.1.3 排列活动顺序8.1.4 估算活动资源8.1.5 估算活动持续时间8.1.6 制定进度计划8.1.7 控制进度 8.2 注意与问题 上篇&#xff1a;第七章、范围管理 第八章 进度管理 8.1 主要过程 包括&#xff1a; 规划进…...

【分布式】分布式唯一 ID 的 几种生成方案以及优缺点snowflake优化方案

在互联网的业务系统中&#xff0c;涉及到各种各样的ID&#xff0c;如在支付系统中就会有支付ID、退款ID等。那一般生成ID都有哪些解决方案呢&#xff1f;特别是在复杂的分布式系统业务场景中&#xff0c;我们应该采用哪种适合自己的解决方案是十分重要的。下面我们一一来列举一…...

FFmpeg5.0源码阅读——av_interleaved_write_frame

摘要&#xff1a;本文主要详细描述FFmpeg中封装时写packet到媒体文件的函数av_interleaved_write_frame的实现。   关键字&#xff1a;av_interleaved_write_frame   读者须知&#xff1a;读者需要熟悉ffmpeg的基本使用。 1 基本调用流程 av_interleaved_write_frame的基本…...

力扣 70. 爬楼梯

题目来源&#xff1a;https://leetcode.cn/problems/climbing-stairs/description/ C题解&#xff08;来源代码随想录&#xff09;&#xff1a; 本质上是一道斐波那契数题。 动规五部曲&#xff1a;定义一个一维数组来记录不同楼层的状态 确定dp数组以及下标的含义。dp[i]&am…...

AVFoundation - 媒体捕捉

文章目录 注意使用 NSCameraUsageDescriptioniOS 的摄像头可能比 Mac 更多功能特性@interface Capture ()<AVCaptureFileOutputRecordingDelegate>@property (strong, nonatomic) AVCaptureSession *captureSession; @property (weak, nonatomic) AVCaptureDeviceInput *…...

【新版系统架构补充】-嵌入式技术

嵌入式微处理体系结构 冯诺依曼结构 传统计算机采用冯诺依曼结构&#xff0c;也称普林斯顿结构&#xff0c;是一种将程序指令存储器和数据存储器合并在一起的存储器结构 冯诺依曼的计算机程序和数据共用一个存储空间&#xff0c;程序指令存储地址和数据存储地址指向同一个存…...

fpga开发--蜂鸣器发出连续不同的音调

描述 使用fpga蜂鸣器连续发出do&#xff0c;re&#xff0c;mi&#xff0c;fa&#xff0c;so&#xff0c;la&#xff0c;xi七个不同的音调&#xff0c;每个音调的持续时间为0.5s。 思路 采用状态机实现音调的转化&#xff0c;当do状态持续了0.5s之后转移到re状态&#xff0c;…...

Redis 主从同步原理

一、什么是主从同步&#xff1f; 主从同步&#xff0c;就是将数据冗余备份&#xff0c;主库&#xff08;Master&#xff09;将自己库中的数据&#xff0c;同步给从库&#xff08;Slave&#xff09;。 从库可以一个&#xff0c;也可以多个&#xff0c;如图所示&#xff1a; 二…...

opencv-28 自适应阈值处理-cv2.adaptiveThreshold()

什么是自适应阈值处理? 对于色彩均衡的图像&#xff0c;直接使用一个阈值就能完成对图像的阈值化处理。但是&#xff0c;有时图像的色彩是不均衡的&#xff0c;此时如果只使用一个阈值&#xff0c;就无法得到清晰有效的阈值分割结果图像。 有一种改进的阈值处理技术&#xff…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

Qwen系列之Qwen3解读:最强开源模型的细节拆解

文章目录 1.1分钟快览2.模型架构2.1.Dense模型2.2.MoE模型 3.预训练阶段3.1.数据3.2.训练3.3.评估 4.后训练阶段S1: 长链思维冷启动S2: 推理强化学习S3: 思考模式融合S4: 通用强化学习 5.全家桶中的小模型训练评估评估数据集评估细节评估效果弱智评估和民间Arena 分析展望 如果…...

用鸿蒙HarmonyOS5实现国际象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的国际象棋小游戏的完整实现代码&#xff0c;使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├── …...