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

Leetcode : 215. 数组中的第 K 个最大元素

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路:最开始排序算法,弄完之后直接按照要求选择,可惜题目对时间复杂度有要求,只能上快排,但是快排并不是直接满足,还需要在基础上优化。快排采取分治的思想,正常递归需要子串都进行排序,最后合并,但是找出结果有个便利的点就是可以判断在那个串里面,选择性的进行快排来加速。

#include <iostream>
#include <vector>using namespace std;
//选择排序
// class Solution {
// public:
//     int findKthLargest(vector<int>& nums, int k) {
//         for (int i = 0; i < nums.size(); i++){
//             int min_index = i; // 记录最小值的索引
//             for (int j = i; j < nums.size(); j++){
//                 if (nums[j] < nums[min_index]){
//                     min_index = j;
//                 }
//             }
//             swap(nums[min_index], nums[i]);
//         }
//         return nums[nums.size() - k];
//     }
// };class Solution {
public:int aparthSort(vector<int>& nums, int left, int right){int i = left, j = right;int pivot = nums[left];while (i < j) {while (i < j) {if (nums[j] < pivot) {nums[i] = nums[j];i++;break;}else j--;}while (i < j) {if (nums[i] > pivot) {nums[j] = nums[i];j--;break;}elsei++;}}nums[i] = pivot;return i;}int sort (vector<int>& nums, int left, int right, int k) {int mid;if (left < right){mid = aparthSort(nums, left, right);if (mid == nums.size() - k) return nums[mid];else if (mid > nums.size() - k) return sort(nums, left, mid - 1, k);else return sort(nums, mid + 1, right, k);}else    return nums[nums.size() - k];}int findKthLargest(vector<int>& nums, int k) {int res =  sort(nums, 0, nums.size() - 1, k);return res;}
};int main(){Solution s;vector<int> nums = {3,2,1,5,6,4};// vector<int> nums = {1};int k = 4;cout << s.findKthLargest(nums, k) << endl;for (int i = 0; i < nums.size(); i++){cout << nums[i] << " ";}return 0;
}

相关文章:

Leetcode : 215. 数组中的第 K 个最大元素

给定整数数组 nums 和整数 k&#xff0c;请返回数组中第 k 个最大的元素。 请注意&#xff0c;你需要找的是数组排序后的第 k 个最大的元素&#xff0c;而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 思路&#xff1a;最开始排序算法&…...

node express实现Excel文档转json文件

有些场景我们需要将Excel文档中的内容抽取出来生成别的文件&#xff0c;作为一个前端&#xff0c;服务框架最应该熟悉的就是node了&#xff0c;以下是基于多语言转换实现代码&#xff0c;看明白原理自己改一改就能用了 1.安装node环境 2.创建一个文件夹&#xff0c;文件夹中创建…...

【算法分析与设计】最大二叉树

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;算法分析与设计 ⛺️稳中求进&#xff0c;晒太阳 题目 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点&#xff0c;其值为 nums 中的最…...

面试问答总结之并发编程

文章目录 &#x1f412;个人主页&#x1f3c5;JavaEE系列专栏&#x1f4d6;前言&#xff1a;&#x1f380;多线程的优点、缺点&#x1f415;并发编程的核心问题 &#xff1a;不可见性、乱序性、非原子性&#x1fa80;不可见性&#x1fa80;乱序性&#x1fa80;非原子性&#x1…...

红外测温仪芯片方案开发设计

红外测温仪由光学系统、光电探测器、信号放大器及信号处理、显示输出等部分组成。光学系统汇集其视场内的目标红外辐射能量&#xff0c;视场的大小由测温仪的光学零件以及位置决定。被测物体辐射的红外首先进入测温仪的光学系统&#xff0c;再由光学系统汇聚射入的红外线&#…...

五、数组——Java基础篇

五、数组 1、数组元素的遍历 1.1数组的遍历&#xff1a;将数组内的元素展现出来 1、普通for遍历&#xff1a;根据下表获取数组内的元素 2、增强for遍历&#xff1a; for&#xff08;数据元素类型 变量名&#xff1a;数组名&#xff09;{ 变量名&#xff1a;数组内的每一个值…...

如何用golang写一个自己的后端框架

如果你想要不使用任何现有的后端框架,完全从头开始创建一个后端框架,你需要实现Web服务器的基本组件,比如路由器、请求处理、中间件支持等。以下是一个简单的指南,用于创建一个基本的、不使用任何外部框架的Go后端框架。 步骤 1: 设置工作环境 确保你已经安装了Go语言环境…...

linux 如何给服务器批量做免密,如何批量挂在磁盘

前提条件 所有机器网络互通&#xff0c;且已做了免密登录 linux服务器批量做免密脚本如下 #!/bin/bash # 定义服务器列表文件 SERVERS_FILE"host" # 定义生成的密钥的存储目录 KEY_DIR"/root/.ssh" # 检查是否输入了文件路径 if [ $# -ne 1 ]; then …...

Android Activity的生命周期详解

在Android开发中&#xff0c;了解Activity的生命周期是非常重要的&#xff0c;它决定了Activity在不同状态下的行为和处理逻辑。Android中的Activity生命周期包括多个方法&#xff0c;每个方法都代表了Activity在特定状态下的行为。下面我们来逐一介绍这些方法及其对应的生命周…...

python学习笔记-内置类型

Python内置类型是Python编程语言中自带的基本数据类型&#xff0c;它们用于存储和处理数据。其中包括数字、序列、映射、类、实例和异常等主要类型。 在这些内置类型中&#xff0c;有一些是可变的&#xff0c;它们具有修改自身内容的能力&#xff0c;比如添加、移除或重排成员…...

校园微社区微信小程序源码/二手交易/兼职交友微信小程序源码

云开发校园微社区微信小程序开源源码&#xff0c;这是一款云开发校园微社区-二手交易_兼职_交友_项目微信小程序开源源码&#xff0c;可以给你提供快捷方便的校园生活&#xff0c;有很多有趣实用的板块和功能&#xff0c;如&#xff1a;闲置交易、表白交友、疑问互答、任务兼职…...

如何在 Angular 中使用 NgTemplateOutlet 创建可重用组件

简介 单一职责原则是指应用程序的各个部分应该只有一个目的。遵循这个原则可以使您的 Angular 应用程序更容易测试和开发。 在 Angular 中&#xff0c;使用 NgTemplateOutlet 而不是创建特定组件&#xff0c;可以使组件在不修改组件本身的情况下轻松修改为各种用例。 在本文…...

改进的yolo交通标志tt100k数据集目标检测(代码+原理+毕设可用)

YOLO TT100K: 基于YOLO训练的交通标志检测模型 在原始代码基础上&#xff1a; 修改数据加载类&#xff0c;支持CoCo格式&#xff08;使用cocoapi&#xff09;&#xff1b;修改数据增强&#xff1b;validation增加mAP计算&#xff1b;修改anchor&#xff1b; 注: 实验开启weig…...

nginx 日志,压缩,https功能介绍

一&#xff0c; 自定义访问日志 &#xff08;一&#xff09;日志位置存放 1&#xff0c;格式 2&#xff0c; 级别 level: debug, info, notice, warn, error, crit, alert, emerg 3&#xff0c;示例 服务机定义 错误日志存放位置 客户机错误访问 查看错误日志 4&#xff…...

代码随想录三刷day17

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣144. 二叉树的前序遍历二、力扣145. 二叉树的后序遍历三、力扣94. 二叉树的中序遍历四、力扣144. 二叉树的前序遍历无、力扣145. 二叉树的后序遍历六、…...

postcss-px-to-viewport include属性

包含include配置的(github)&#xff1a;npm i https://github.com/evrone/postcss-px-to-viewport -S 包含include配置的(npm)&#xff1a;npm i postcss-px-to-viewport-8-with-include -S 不包含包include配置的(npm)&#xff1a;npm i postcss-px-to-viewport 看了一下这篇文…...

C++设计模式——抽象工厂模式

文章目录 抽象工厂模式的主要组成部分抽象工厂模式的一个典型例子抽象工厂模式用于其他场景抽象工厂模式与其他设计模式结合使用 C 中的抽象工厂模式是一种创建型设计模式&#xff0c;它主要用于处理对象家族的创建&#xff0c;这些对象之间可能存在一定的关联关系或属于相同的…...

Windows安装VNC连接工具并结合cpolar实现远程内网Ubuntu系统桌面

文章目录 前言1. ubuntu安装VNC2. 设置vnc开机启动3. windows 安装VNC viewer连接工具4. 内网穿透4.1 安装cpolar【支持使用一键脚本命令安装】4.2 创建隧道映射4.3 测试公网远程访问 5. 配置固定TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网TCP端口地址5.3 测试…...

Vue3 Hooks函数使用及封装思想

一、什么是Hooks函数&#xff1f; 想象一下&#xff0c;你在做饭&#xff0c;有一些调料你经常会用到&#xff0c;比如盐、酱油和辣椒。每次做饭时&#xff0c;你都会从柜子里拿出这些调料。如果你每次用完都把它们随便放在厨房的某个角落&#xff0c;下次做饭时就可能找不到它…...

YOLOv8改进涨点,添加GSConv+Slim Neck,有效提升目标检测效果,代码改进(超详细)

目录 摘要 主要想法 GSConv GSConv代码实现 slim-neck slim-neck代码实现 yaml文件 完整代码分享 总结 摘要 目标检测是计算机视觉中重要的下游任务。对于车载边缘计算平台来说&#xff0c;巨大的模型很难达到实时检测的要求。而且&#xff0c;由大量深度可分离卷积层构…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...