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

Leetcode215. 数组中的第K个最大元素(HOT100)

链接

第一次:

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {sort(nums.begin(),nums.end());int n = nums.size();return nums[n-k];}
};

这显然不能出现在面试中,因为面试官考察的不是这个。

正确的代码:

class Solution{public:int quick_sort(vector<int>& nums,int l,int r,int k){if(l==r)return nums[k];//会保证第k小的数一直在递归的区间中,那么当区间里只有一个数的时候,就一定是要找的数了。int x = nums[l],i = l-1,j = r+1;while(i<j){do i++;while(nums[i]>x);do j--;while(nums[j]<x);if(i<j)swap(nums[i],nums[j]);}if(k<=j)return quick_sort(nums,l,j,k);else return quick_sort(nums,j+1,r,k);}int findKthLargest(vector<int>& nums,int k){return quick_sort(nums,0,nums.size()-1,k-1);//第k大,比如第1大,其实是降序排序后,索引为0的元素,第2大,就是索引为1的元素。//此题如果改为,找出第k小的元素,那么只需将do while(翻转这里的符号即可);}
};

使用的是快速选择算法,本质还是快排。 

快速选择算法具体而言:

1.先找个目标值也就是题目中的x,将数组分到两边,此时x左边都<=x,右边>=x
2.查看k是否<=左边个数,如果小于说明在左侧内,左侧递归排序即可找到K。反之在右边
3.最终无限夹击找到K

相关文章:

Leetcode215. 数组中的第K个最大元素(HOT100)

链接 第一次&#xff1a; class Solution { public:int findKthLargest(vector<int>& nums, int k) {sort(nums.begin(),nums.end());int n nums.size();return nums[n-k];} }; 这显然不能出现在面试中&#xff0c;因为面试官考察的不是这个。 正确的代码&#…...

QT与嵌入式——搭建串口

1、源码 由于我需要不止一个串口来进行数据交互&#xff0c;所以简单的封装了一下 void Usb_Init(QString portName, QSerialPort *Port) {Port->setPortName(portName);Port->setBaudRate(QSerialPort::Baud115200); // 设置波特率&#xff0c;根据你的开发板配置修改…...

Shell编程-6

声明&#xff1a;学习视频来自b站up主 泷羽sec&#xff0c;如涉及侵权马上删除文章 感谢泷羽sec 团队的教学 视频地址&#xff1a;shell(6)if条件判断与for循环结构_哔哩哔哩_bilibili 一、if条件判断 在Shell脚本中&#xff0c;if语句用于基于条件的评估来执行不同的代码块。…...

使用 Postman 设置 Bearer Token 进行身份验证

学习笔记 1. 打开 Postman 并创建新请求 打开 Postman。 在左上角点击 按钮&#xff0c;创建一个新的请求。 2. 选择 HTTP 方法 在请求类型&#xff08;默认为 GET&#xff09;旁边的下拉菜单中&#xff0c;选择你需要的 HTTP 方法&#xff0c;如 POST、GET、PUT 等。 3…...

现在转前端怎么样?

互联网技术日新月异&#xff0c;软件开发者追逐技术浪潮的脚步从未停歇。在这个快速发展的行业中&#xff0c;如何规划自己的职业道路&#xff0c;选择合适的技术方向&#xff0c;成为了许多开发者面临的重要抉择。本文将围绕技术选择这个话题&#xff0c;分享一些深入的思考和…...

【算法一周目】滑动窗口(1)

目录 长度最小的子数组 解题思路 代码实现 无重复字符的最大字串 解题思路 代码实现 最大连续1的个数l l l 解题思路 代码实现 将x减到0的最小操作数 解题思路 代码实现 长度最小的子数组 题目链接&#xff1a;209. 长度最小的子数组题目描述&#xff1a; 给定一个…...

React Native 基础

React 的核心概念 定义函数式组件 import组件 要定义一个Cat组件,第一步要使用 import 语句来引入React以及React Native的 Text 组件: import React from react; import { Text } from react-native; 定义函数作为组件 const CatApp = () => {}; 渲染Text组件...

【C++笔记】list使用详解及模拟实现

前言 各位读者朋友们大家好&#xff01;上期我们讲了vector的使用以及底层的模拟实现&#xff0c;这期我们来讲list。 目录 前言一. list的介绍及使用1.1 list的介绍1.2 list的使用1.2.1 list的构造1.2.2 list iterator的使用1.2.3 list capacity1.2.4 list element access1.…...

【机器学习】机器学习中用到的高等数学知识-7.信息论 (Information Theory)

熵 (Entropy)&#xff1a;用于评估信息的随机性&#xff0c;常用于决策树和聚类算法。交叉熵 (Cross-Entropy)&#xff1a;用于衡量两个概率分布之间的差异&#xff0c;在分类问题中常用。 信息论作为处理信息量和信息传输的数学理论&#xff0c;在机器学习中具有广泛的应用。…...

《现代制造技术与装备》是什么级别的期刊?是正规期刊吗?能评职称吗?

​问题解答 问&#xff1a;《现代制造技术与装备》是不是核心期刊&#xff1f; 答&#xff1a;不是&#xff0c;是知网收录的第二批认定学术期刊。 问&#xff1a;《现代制造技术与装备》级别&#xff1f; 答&#xff1a;省级。主管单位&#xff1a;齐鲁工业大学&#xff0…...

09 - Clickhouse的SQL操作

目录 1、Insert 1.1、标准 1.2、从表到表的插入 2、Update和Delete 2.1、删除操作 2.2、修改操作 3、查询操作 3.1、with rollup&#xff1a;从右至左去掉维度进行小计 3.2、with cube : 从右至左去掉维度进行小计&#xff0c;再从左至右去掉维度进行小计 3.3、with …...

如何解决pdf.js跨域从url动态加载pdf文档

摘要 当我们想用PDF.js从URL加载文档时&#xff0c;将会因遇到跨域问题而中断&#xff0c;且是因为会触发了PDF.js和浏览器的双重CORS block&#xff0c;这篇文章将会介绍&#xff1a;①如何禁用pdf.js的跨域&#xff1f;②如何绕过浏览器的CORS加载URL文件&#xff1f;②如何使…...

深入理解TTY体系:设备节点与驱动程序框架详解

往期内容 本专栏往期内容&#xff1a;Uart子系统 UART串口硬件介绍 interrupt子系统专栏&#xff1a; 专栏地址&#xff1a;interrupt子系统Linux 链式与层级中断控制器讲解&#xff1a;原理与驱动开发 – 末片&#xff0c;有专栏内容观看顺序 pinctrl和gpio子系统专栏&#xf…...

库的操作(MySQL)

1.创建数据库 语法&#xff1a; CREATE DATABASE [IF NOT EXISTS] db_name [create_specification [, create_specification] ...] create_specification:[DEFAULT] CHARACTER SET charset_name[DEFAULT] COLLATE collation_name说明&#xff1a; 大写的表示关键字 [ ] 是可…...

在 for 循环中,JVM可能会将 arr.length 提升到循环外部,仅计算一次。可能会将如何解释 详解

在 Java 的 for 循环中&#xff0c;JVM 有能力进行优化&#xff0c;将 arr.length 的访问提升到循环外部&#xff0c;避免每次迭代都重新计算 arr.length。这种优化主要是由于 JVM 的 即时编译器&#xff08;JIT&#xff09; 和 逃逸分析&#xff08;Escape Analysis&#xff0…...

回溯--数据在内存中的存储:整数、大小端和浮点数的深度解析

目录 引言 1. 整数在内存中的存储 1.1 原码、反码和补码 1.2 为什么使用补码&#xff1f; 1.3 示例代码&#xff1a;整数的存储 2. 大小端字节序和字节序判断 2.1 什么是大端和小端&#xff1f; 2.2 为什么会有大端和小端之分&#xff1f; 2.3 字节序的判断小程序 2.…...

第二十二章 Spring之假如让你来写AOP——Target Object(目标对象)篇

Spring源码阅读目录 第一部分——IOC篇 第一章 Spring之最熟悉的陌生人——IOC 第二章 Spring之假如让你来写IOC容器——加载资源篇 第三章 Spring之假如让你来写IOC容器——解析配置文件篇 第四章 Spring之假如让你来写IOC容器——XML配置文件篇 第五章 Spring之假如让你来写…...

探索设计模式:原型模式

设计模式之原型模式 &#x1f9d0;1. 概念&#x1f3af;2. 原型模式的作用&#x1f4e6;3. 实现1. 定义原型接口2. 定义具体的原型类3. 定义客户端4. 结果 &#x1f4f0; 4. 应用场景&#x1f50d;5. 深拷贝和浅拷贝 在面向对象编程中&#xff0c;设计模式是一种通用的解决方案…...

NLP论文速读(EMNLP 2023)|工具增强的思维链推理

论文速读|ChatCoT: Tool-Augmented Chain-of-Thought Reasoning on Chat-based Large Language Models 论文信息&#xff1a; 简介&#xff1a; 本文背景是关于大型语言模型&#xff08;LLMs&#xff09;在复杂推理任务中的表现。尽管LLMs在多种评估基准测试中取得了优异的成绩…...

JVM垃圾回收详解.②

空间分配担保 空间分配担保是为了确保在 Minor GC 之前老年代本身还有容纳新生代所有对象的剩余空间。 《深入理解 Java 虚拟机》第三章对于空间分配担保的描述如下&#xff1a; JDK 6 Update 24 之前&#xff0c;在发生 Minor GC 之前&#xff0c;虚拟机必须先检查老年代最大…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...