当前位置: 首页 > 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;由大量深度可分离卷积层构…...

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

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

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...