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

【LeetCode: 215. 数组中的第K个最大元素 + 快速选择排序】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述
在这里插入图片描述

🍔 目录

    • 🚩 题目链接
    • ⛲ 题目描述
    • 🌟 求解思路&实现代码&运行结果
      • ⚡ 快速选择排序
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
    • 💬 共勉

🚩 题目链接

  • 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 <= 105
-104 <= nums[i] <= 104

🌟 求解思路&实现代码&运行结果


⚡ 快速选择排序

🥦 求解思路
  1. 题目要求在一个未排序的数组中找到第 k 个最大的元素。可以通过找到第 n - k 个最小的元素来等价求解(其中 n 是数组的长度)。

  2. 基于快速选择算法:利用快速排序的分区思想,通过随机选择基准值(pivot)将数组划分为三部分:

    • 小于 pivot 的部分。

    • 等于 pivot 的部分。

    • 大于 pivot 的部分。

  3. 递归处理:

    • 如果目标索引 index 在等于 pivot 的范围内,则直接返回 pivot。

    • 如果目标索引 index 在小于 pivot 的范围内,则在左半部分递归查找。

    • 如果目标索引 index 在大于 pivot 的范围内,则在右半部分递归查找。

  4. 随机化基准值:通过随机选择基准值,避免最坏情况的时间复杂度。

  5. 有了基本的思路,接下来我们就来通过代码来实现一下。

🥦 实现代码
class Solution {public int findKthLargest(int[] nums, int k) {return minKth(nums, nums.length - k);}public static int minKth(int[] arr, int k) {return process(arr, 0, arr.length - 1, k);}public static int process(int[] arr, int L, int R, int index) {if (L == R) {return arr[L];}int pivot = arr[L + (int) (Math.random() * (R - L + 1))];int[] range = partition(arr, L, R, pivot);if (index >= range[0] && index <= range[1]) {return arr[index];} else if (index < range[0]) {return process(arr, L, range[0] - 1, index);} else {return process(arr, range[1] + 1, R, index);}}public static int[] partition(int[] arr, int L, int R, int pivot) {int less = L - 1;int more = R + 1;int cur = L;while (cur < more) {if (arr[cur] < pivot) {swap(arr, ++less, cur++);} else if (arr[cur] > pivot) {swap(arr, cur, --more);} else {cur++;}}return new int[] { less + 1, more - 1 };}public static void swap(int[] arr, int i1, int i2) {int tmp = arr[i1];arr[i1] = arr[i2];arr[i2] = tmp;}}
🥦 运行结果

在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

相关文章:

【LeetCode: 215. 数组中的第K个最大元素 + 快速选择排序】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…...

GraphRAG: Auto Prompt Tuning 实践

GraphRAG 的 Auto Prompt Tuning 功能是一个强大的工具&#xff0c;用于优化知识图谱的生成过程。以下是对该功能的详细介绍和分析&#xff1a; 自动提示调优&#xff08;Auto Prompt Tuning&#xff09; 1. 概念 GraphRAG 的自动提示调优功能旨在为特定领域的知识图谱生成创…...

提示词的艺术----AI Prompt撰写指南(个人用)

提示词的艺术 写在前面 制定提示词就像是和朋友聊天一样&#xff0c;要求我们能够清楚地表达问题。通过这个过程&#xff0c;一方面要不断练习提高自己地表达能力&#xff0c;另一方面还要锻炼自己使用更准确精炼的语言提出问题的能力。 什么样的提示词有用&#xff1f; 有…...

Tensor 基本操作1 | PyTorch 深度学习实战

目录 创建 Tensor常用操作unsqueezesqueezeSoftmax代码1代码2代码3 argmaxitem 创建 Tensor 使用 Torch 接口创建 Tensor import torch参考&#xff1a;https://pytorch.org/tutorials/beginner/basics/tensorqs_tutorial.html 常用操作 unsqueeze 将多维数组解套&#xf…...

CSS 的基础知识及应用

前言 CSS&#xff08;层叠样式表&#xff09;是网页设计和开发中不可或缺的一部分。它用于描述网页的视觉表现&#xff0c;使页面不仅实现功能&#xff0c;还能提供吸引人的用户体验。本文将介绍 CSS 的基本概念、语法、选择器及其在提升网页美观性方面的重要性。 什么是 CSS&…...

贪心算法(题1)区间选点

输出 2 #include <iostream> #include<algorithm>using namespace std;const int N 100010 ;int n; struct Range {int l,r;bool operator <(const Range &W)const{return r<W.r;} }range[N];int main() {scanf("%d",&n);for(int i0;i&l…...

CamemBERT:一款出色的法语语言模型

摘要 预训练语言模型在自然语言处理中已无处不在。尽管这些模型取得了成功&#xff0c;但大多数可用模型要么是在英语数据上训练的&#xff0c;要么是在多种语言数据拼接的基础上训练的。这使得这些模型在除英语以外的所有语言中的实际应用非常有限。本文探讨了为其他语言训练…...

解决 IntelliJ IDEA 项目包后出现“% classes”和“% lines covered”的问题

前言 在使用 IntelliJ IDEA 开发 Java 或其他支持的语言时&#xff0c;您可能会遇到项目包后面意外地出现了“% classes”和“% lines covered”的信息。这些百分比表示的是代码覆盖率&#xff08;Coverage&#xff09;&#xff0c;它们展示了您的测试覆盖了多少比例的类和代码…...

Matlab总提示内存不够用,明明小于电脑内存

目录 前言情况1&#xff08;改matlab最大内存限制&#xff09;情况2&#xff08;重启电脑&#xff09;情况3 前言 在使用matlab中&#xff0c;有时候需要占用的内存并没有超过电脑内存依旧会报错&#xff0c;提示内存不够用&#xff0c;可以尝试下面几种方法&#xff0c;总有一…...

Py之cv2:cv2(OpenCV,opencv-python)库的简介、安装、使用方法(常见函数、图像基本运算等)

1. OpenCV简介 1.1 OpenCV定义与功能 OpenCV&#xff08;Open Source Computer Vision Library&#xff09;是一个开源的计算机视觉和机器学习软件库。它为计算机视觉应用程序提供了一个通用的基础设施&#xff0c;并加速了在商业产品中使用机器感知。作为BSD许可的产品&…...

leetcode707-设计链表

leetcode 707 思路 本题也是用了虚拟头节点来进行解答&#xff0c;这样的好处是&#xff0c;不管是头节点还是中间的节点都可以当成是中间节点来处理&#xff0c;用同一套方法就可以进行处理&#xff0c;而不用考虑太多的边界条件。 下面题目中最主要的实现就是添加操作addA…...

Linux操作命令之云计算基础命令

一、图形化界面/文本模式 ctrlaltF2-6 图形切换到文本 ctrlalt 鼠标跳出虚拟机 ctrlaltF1 文本切换到图形 shift ctrl "" 扩大 ctrl "-" 缩小 shift ctrl "n" 新终端 shift ctrl "t" 新标签 alt 1,…...

HTML<bdo>标签

例子 指定文本方向&#xff1a; <bdo dir"rtl"> This text will go right-to-left. </bdo> <!DOCTYPE html> <html> <body> <h1>The bdo element</h1> <p>This paragraph will go left-to-right.</p> …...

将IDLE里面python环境pyqt5配置的vscode

首先安装pyqt5全套&#xff1a;pip install pyqt5-tools 打开Vscode&#xff1a; 安装第三方扩展&#xff1a;PYQT Integration 成功配置designer.exe的路径【个人安装pyqt5的执行路径】&#xff0c;便可直接打开UI文件&#xff0c;进行编辑。 配置pyuic,如果下图填写方法使用…...

【C++】结构体(下)

4、结构体指针 作用&#xff1a;通过指针访问结构体中的成员 利用操作符“----->”可以通过结构体指针访问结构体成员。 示例&#xff1a; #include<iostream> #include<string> using namespace std; struct student {//姓名string name;//年龄int age;//分数…...

YOLOv10-1.1部分代码阅读笔记-dataset.py

dataset.py ultralytics\data\dataset.py 目录 dataset.py 1.所需的库和模块 2.class YOLODataset(BaseDataset): 3.class ClassificationDataset(torchvision.datasets.ImageFolder): 4.def load_dataset_cache_file(path): 5.def save_dataset_cache_file(prefix,…...

【电视盒子】HI3798MV300刷机教程笔记/备份遥控码修复遥控器/ADB/线刷卡刷/电视盒子安装第三方应用软件

心血来潮&#xff0c;看到电视机顶盒满天飞的广告&#xff0c;想改造一下家里的电视盒子&#xff0c;学一下网上的人刷机&#xff0c;但是一切都不知道怎么开始&#xff0c;虽然折腾了一天&#xff0c;以失败告终&#xff0c;还是做点刷机笔记。 0.我的机器 年少不会甄别&…...

Mixly米思齐1.0 2.0 3.0 软件windows版本MAC苹果电脑系统安装使用常见问题与解决

Mixly软件应用常见问题 Mixly米思齐编译或上传报错&#xff1f; 1、软件安装与驱动&#xff08;Mixly1-2&#xff09; 1-1 Windows版本 软件及驱动可以在Mixly群&#xff08;QQ群号621937623&#xff09;的群文件夹中找到&#xff0c;或到Mixly在线软件下载链接中重新下安装…...

在 QNAP NAS中使用 Container Station 运行 Docker 的完整指南

QNAP 为用户提供了一个名为 Container Station 的应用&#xff0c;它在 QNAP NAS 上将 Docker 和 LXC 结合在一起&#xff0c;通过图形化界面&#xff0c;让用户更轻松地在 NAS 上管理容器。本文将带你一步步了解如何在 QNAP NAS 上安装和使用 Container Station&#xff0c;以…...

Spark RPC 学习总结

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff1a;https://www.captainai.net/dongkelun 前言 本文从API层面学习总结Spark RPC,暂不涉及源码分析。 Spark 通信历史 最开始: …...

JAVA安全—JWT攻防Swagger自动化Druid泄露

前言 依旧是Java安全的内容&#xff0c;今天主要是讲JWT这个东西&#xff0c;JWT之前讲过了&#xff0c;是Java中特有的身份校验机制&#xff0c;原理我就不再多说了&#xff0c;主要是看看它的安全问题&#xff0c;至于Swagger和Druid顺便讲一下。 Druid泄露 Druid是阿里巴…...

深度学习核函数

一、核函数的基本概念 核函数在机器学习中具有重要应用价值&#xff0c;常用于支持向量机&#xff08;SVM&#xff09;等算法中。 核函数是面试中经常被考到的知识点&#xff0c;对于找工作和实际数据转换都有重要作用。 二、数据建模与核函数的作用 数据越多&#xff0c;可…...

【神经网络基础】

目录 一、神经网络的构成 1.1什么是神经网络&#xff1f; 1.2 激活函数 1.2.1 Sigmoid 1.2.2 Tanh 1.2.3 ReLU 1.2.4 softmax 1.2.5 其他激活函数 1.2.6 选择激活函数 1.3 参数初始化 1.4 模型构建 二、损失函数 2.1 分类问题 2.1.1多分类&#xff08;多分类交叉…...

一些面试常见问题及其回答参考

1、请你自我介绍一下你自己&#xff1f; 回答提示&#xff1a;一般人回答这个问题过于平常&#xff0c;只说姓名、年龄、爱好、工作经验&#xff0c;这些在简历上都有。其实&#xff0c;企业最希望知道的是求职者能否胜任工作&#xff0c;包括&#xff1a;最强的技能、最深入研…...

[JavaScript] 深入理解流程控制结构

文章目录 1. **if-else 语句**基本语法&#xff1a;示例&#xff1a;扩展&#xff1a;else if 2. **switch-case 语句**基本语法&#xff1a;示例&#xff1a;注意事项&#xff1a; 3. **for 循环**基本语法&#xff1a;示例&#xff1a;扩展&#xff1a;for-in 和 for-of 4. *…...

Mysql常见问题处理集锦

Mysql常见问题处理集锦 root用户密码忘记&#xff0c;重置的操作(windows上的操作)MySQL报错&#xff1a;ERROR 1118 (42000): Row size too large. 或者 Row size too large (&#xff1e; 8126).场景&#xff1a;报错原因解决办法 详解行大小限制示例&#xff1a;内容来源于网…...

高级java每日一道面试题-2025年01月19日-框架篇[Mybatis篇]-MyBatis 中见过什么设计模式 ?

如果有遗漏,评论区告诉我进行补充 面试官: MyBatis 中见过什么设计模式 ? 我回答: 1. 工厂模式&#xff08;Factory Pattern&#xff09; 定义&#xff1a;工厂模式是一种创建型模式&#xff0c;它提供了一种创建对象的最佳方式&#xff0c;将对象创建过程抽象化&#xff…...

C++,设计模式,【目录篇】

文章目录 1. 简介2. 设计模式的分类2.1 创建型模式&#xff08;Creational Patterns&#xff09;&#xff1a;2.2 结构型模式&#xff08;Structural Patterns&#xff09;&#xff1a;2.3 行为型模式&#xff08;Behavioral Patterns&#xff09;&#xff1a; 3. 使用设计模式…...

C/C++内存管理(超详解)

目录 1.C/C内存分布 2.C语言动态内存管理 2.1 malloc 2.2 free 2.3 calloc 2.4 realloc 3.C动态内存管理 3.1new/delete操作内置类型 3.2new/delete操作自定义类型 3.3operator new与operator delete函数 3.4定位new表达式(placement-new) 1.C/C内存分布 内存中是如…...

【前端】用OSS增强Hexo的搜索功能

文章目录 前言配置 _config.fluid.yml云端实时更新 local-search.xml解决 OSS.Bucket 的跨域问题 前言 原文地址&#xff1a;https://blog.dwj601.cn/FrontEnd/Hexo/hexo-enhance-local-search-with-oss/ 考虑到某著名云服务商提供的云服务器在两年的 99 计划后续费价格高达四…...

智慧校园平台中的信息处理与技术应用

随着信息技术的迅速发展&#xff0c;智慧校园平台已经成为现代教育领域的重要组成部分。智慧校园平台不仅能够提高教学效率&#xff0c;还能够改善学生的学习体验&#xff0c;以及优化学校的管理流程。为了实现这些目标&#xff0c;信息处理技术在智慧校园平台的应用中扮演了至…...

Spring MVC(一)

RestController RestController 是由 Controller 和 ResponseBody 两个注解构成的。 Spring 启动的时候会扫描所有包含 Controller 或者 RestController 注解的类&#xff0c;创建出对外的接口&#xff0c;这样外界就可以从这里与服务器实现交互&#xff0c;如果没有这个注解…...

【王树森搜索引擎技术】概要01:搜索引擎的基本概念

1. 基本名词 query&#xff1a;查询词SUG&#xff1a;搜索建议文档&#xff1a;搜索结果标签/筛选项 文档单列曝光 文档双列曝光 2. 曝光与点击 曝光&#xff1a;用户在搜索结果页上看到文档&#xff0c;就算曝光文档点击&#xff1a;在曝光后&#xff0c;用户点击文档&…...

imbinarize函数用法详解与示例

一、函数概述 众所周知&#xff0c;im2bw函数可以将灰度图像转换为二值图像。但MATLAB中还有一个imbinarize函数可以将灰度图像转换为二值图像。imbinarize函数是MATLAB图像处理工具箱中用于将灰度图像或体数据二值化的工具。它可以通过全局或自适应阈值方法将灰度图像转换为二…...

ThinkPHP 8的一对多关联

【图书介绍】《ThinkPHP 8高效构建Web应用》-CSDN博客 《2025新书 ThinkPHP 8高效构建Web应用 编程与应用开发丛书 夏磊 清华大学出版社教材书籍 9787302678236 ThinkPHP 8高效构建Web应用》【摘要 书评 试读】- 京东图书 使用VS Code开发ThinkPHP项目-CSDN博客 编程与应用开…...

医工交叉合作信息汇总,第三期名单分享,近期需要联合申请基金以及课题合作的老师/同学重点关注一下!|合作信息·25-01-17

小罗碎碎念 之前出过两期医工交叉领域合作信息的汇总推送&#xff0c;最近一直没顾上这事&#xff0c;现在重新捡起来&#xff0c;并且把需求向所有的粉丝公开&#xff0c;直接在后台回复“合作信息”就可以获取表格。 截至目前为止&#xff0c;共收集了92条合作信息&#xf…...

深度学习中的张量 - 使用PyTorch进行广播和元素级操作

深度学习中的张量 - 使用PyTorch进行广播和元素级操作 元素级是什么意思&#xff1f; 元素级操作在神经网络编程中与张量的使用非常常见。让我们从一个元素级操作的定义开始这次讨论。 一个_元素级_操作是在两个张量之间进行的操作&#xff0c;它作用于各自张量中的相应元素…...

浅谈云计算20 | OpenStack管理模块(下)

OpenStack管理模块&#xff08;下&#xff09; 五、存储管理5.1 存储管理概述 5.2 架构设计5.2.1 Cinder块存储架构5.2.2 Swift对象存储架构 六、网络管理6.1 网络管理概述6.2 架构解析6.2.1 Neutron网络服务架构6.2.2 网络拓扑架构 6.3 原理与流程6.3.1 网络创建原理6.3.2 网络…...

GitLab集成Jira

GitLab与Jira集成的两种方式 GitLab 提供了两种 Jira 集成&#xff0c;即Jira议题集成和Jira开发面板集成&#xff0c;可以配置一个或者两个都配置。 具体集成步骤可以参考官方文档Jira 议题集成&#xff08;极狐GitLab文档&#xff09;和Jira 开发面板集成&#xff08;极狐G…...

如何用selenium来链接并打开比特浏览器进行自动化操作(1)

前言 本文是该专栏的第76篇,后面会持续分享python爬虫干货知识,记得关注。 本文,笔者将基于“比特浏览器”,通过selenium来实现链接并打开比特浏览器,进行相关的“自动化”操作。 值得一提的是,在本专栏之前,笔者有详细介绍过“使用selenium或者pyppeteer(puppeteer)…...

Docker私有仓库管理工具Registry

Docker私有仓库管理工具Registry 1 介绍 Registry是私有Docker仓库管理工具&#xff0c;Registry没有可视化管理页面和完备的管理策略。可借助Harbor、docker-registry-browser完成可视化和管理。Harbor是由VMware开发的企业级Docker registry服务。docker-registry-browser是…...

《Hands_On_LLM》8.1 语义搜索和 RAG 概述(Semantic Search and RAG)

说明 接下来的这三篇文章是《On Large Language Models》的第8章&#xff1a;语义搜索和检索增强生成&#xff08;Retrieval-Augmented Generation&#xff09;的翻译。 概述 搜索是最早被业界广泛采用的语言模型应用之一。在开创性论文《BERT&#xff1a;用于语言理解的深度…...

C++实现设计模式---迭代器模式 (Iterator)

迭代器模式 (Iterator) 迭代器模式 是一种行为型设计模式&#xff0c;它提供了一种方法&#xff0c;顺序访问一个聚合对象中的各个元素&#xff0c;而又不需要暴露该对象的内部表示。 意图 提供一种方法&#xff0c;可以顺序访问一个容器对象中的元素&#xff0c;而无需暴露其…...

skywalking的使用

面试常问的面试题&#xff1a; 你们的服务监控怎么做的&#xff1f; 其实就可以回答skywalking&#xff0c;skywalking是一个开源的分布式追踪与性能监视平台&#xff0c;特别适用于微服务架构、云原生环境以及基于容器&#xff08;如Docker、Kubernetes&#xff09;的应用部…...

【C语言系列】深入理解指针(1)

前言 总所周知&#xff0c;C语言中指针部分是非常重要的&#xff0c;这一件我们会介绍指针相关的内容&#xff0c;当然后续我还会出大概4篇与指针相关的文章&#xff0c;来深入的讲解C语言指针部分&#xff0c;希望能够帮助到指针部分薄弱或者根本不会的程序员们&#xff0c;后…...

医院挂号就诊系统设计与实现(代码+数据库+LW)

摘 要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff0c;在计算机上安装医院挂号就诊系统软件来发挥其高效地信息处理的作用&#…...

Mysql 主从复制原理及其工作过程,配置一主两从实验

主从原理&#xff1a;MySQL 主从同步是一种数据库复制技术&#xff0c;它通过将主服务器上的数据更改复制到一个或多个从服务器&#xff0c;实现数据的自动同步。 主从同步的核心原理是将主服务器上的二进制日志复制到从服务器&#xff0c;并在从服务器上执行这些日志中的操作…...

verilog笔记1

1. 阻塞赋值 阻塞赋值&#xff0c;顾名思义即在一个 always 块中&#xff0c;后面的语句会受到前语句的影响&#xff0c;具体来说就是在同一个always 中&#xff0c;一条阻塞赋值语句如果没有执行结束&#xff0c;那么该语句后面的语句就不能被执行&#xff0c;即被“阻塞”。也…...

人工智能之数学基础:线性代数中的线性相关和线性无关

本文重点 在线性代数的广阔领域中,线性相关与线性无关是两个核心概念,它们对于理解向量空间、矩阵运算、线性方程组以及人工智能等问题具有至关重要的作用。 定义与直观理解 当存在一组不全为0的数x1,x2,...,xn使得上式成立的时候,那么此时我们可以说向量组a1,a2...,an…...

Flask简介与安装以及实现一个糕点店的简单流程

目录 1. Flask简介 1.1 Flask的核心特点 1.2 Flask的基本结构 1.3 Flask的常见用法 1.3.1 创建Flask应用 1.3.2 路由和视图函数 1.3.3 动态URL参数 1.3.4 使用模板 1.4 Flask的优点 1.5 总结 2. Flask 环境创建 2.1 创建虚拟环境 2.2 激活虚拟环境 1.3 安装Flask…...