当前位置: 首页 > 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;虚拟机必须先检查老年代最大…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...