nth_element函数——C++快速选择函数
目录
1. 函数原型
2. 功能描述
3. 算法原理
4. 时间复杂度
5. 空间复杂度
6. 使用示例
8. 注意事项
9. 自定义比较函数
11. 总结
nth_element
是 C++ 标准库中提供的一个算法,位于<algorithm>
头文件中,用于部分排序序列。它的主要功能是将序列中第 k 小的元素放到第 k 个位置上,并且保证所有在它之前的元素都不大于它,所有在它之后的元素都不小于它。这个算法的核心思想是基于快速排序的分区操作(Quickselect)。
1. 函数原型
nth_element
的函数原型如下:
template <class RandomIt>
void nth_element(RandomIt first, RandomIt nth, RandomIt last);template <class RandomIt, class Compare>
void nth_element(RandomIt first, RandomIt nth, RandomIt last, Compare comp);
first
:指向序列起始位置的随机访问迭代器。
nth
:指向序列中第 k 个位置的随机访问迭代器。
last
:指向序列结束位置的随机访问迭代器。
comp
(可选):自定义比较函数,默认是std::less
(升序)。
2. 功能描述(无返回值)
(补充:第k大对应第n-k小,对应的下标为n-1-k)
nth_element
的功能是将序列中第 k 小(对应数组下标为k-1)的元素放到第 k 个位置上,并且保证:
-
所有在第 k 个位置之前的元素都不大于第 k 个位置的元素。
-
所有在第 k 个位置之后的元素都不小于第 k 个位置的元素。
3. 算法原理
nth_element
的实现基于快速选择算法(Quickselect),它是快速排序算法的一个变种。其主要步骤如下:
选择支点:从序列中选择一个元素作为支点(pivot)。
分区操作:将序列分为两部分:
小于等于支点的元素放在支点的左边。
大于支点的元素放在支点的右边。
递归处理:
如果支点的位置恰好是 k,则支点就是第 k 小的元素。
如果支点的位置小于 k,则在右边的子序列中递归处理。
如果支点的位置大于 k,则在左边的子序列中递归处理。
4. 时间复杂度
平均时间复杂度:O(n)。
最坏时间复杂度:O(n2),但这种情况很少发生,可以通过随机选择支点来避免。
5. 空间复杂度
-
空间复杂度:O(1),不考虑递归调用的栈空间。
6. 使用示例
以下是一个使用 nth_element
的示例代码,用于找到一个数组中第 k 小的元素:
#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> arr = {7, 10, 4, 3, 20, 15};int k = 3; // 找第 3 小的元素// 使用 nth_elementstd::nth_element(arr.begin(), arr.begin() + k - 1, arr.end());// 输出第 k 小的元素std::cout << "第 " << k << " 小的元素是: " << arr[k - 1] << std::endl;return 0;
}
对于上述代码,输出结果为:
第 3 小的元素是: 7
8. 注意事项
-
nth_element
不会完全排序整个序列,它只保证第 k 小的元素在正确的位置上。 -
如果需要完全排序,可以使用
std::sort
。 -
nth_element
的性能优于完全排序(std::sort
的时间复杂度为 O(nlogn)),特别是在只需要找到第 k 小的元素时。
9. 自定义比较函数
如果需要根据自定义规则进行排序,可以使用自定义比较函数。例如,以下代码按降序找到第 k 大的元素:
#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> arr = {7, 10, 4, 3, 20, 15};int k = 3; // 找第 3 大的元素// 使用 nth_element 和自定义比较函数std::nth_element(arr.begin(), arr.begin() + k - 1, arr.end(), std::greater<int>());// 输出第 k 大的元素std::cout << "第 " << k << " 大的元素是: " << arr[k - 1] << std::endl;return 0;
}
对于上述代码,输出结果为:
第 3 大的元素是: 10
11. 总结
nth_element
是一个非常高效的算法,适用于以下场景:
需要找到序列中第 k 小或第 k 大的元素。
不需要对整个序列进行完全排序。
需要高效地处理大数据量。
收藏加关注,观看不迷路
相关文章:
nth_element函数——C++快速选择函数
目录 1. 函数原型 2. 功能描述 3. 算法原理 4. 时间复杂度 5. 空间复杂度 6. 使用示例 8. 注意事项 9. 自定义比较函数 11. 总结 nth_element 是 C 标准库中提供的一个算法,位于 <algorithm> 头文件中,用于部分排序序列。它的主要功能是将…...
C#接口(Interface)
C#中的接口 接口是C#中一种重要的概念,它定义了一组函数成员,但不实现它们。接口提供了一种标准结构,使得实现接口的类或结构在形式上保持一致。接口定义了属性、方法和事件,这些都是接口的成员,但接口只包含成员的声…...
002 mapper代理开发方式-xml方式
文章目录 代理xml方式UserMapper.javaUser.javadb.propertiesSqlMapConfig.xmlUserMapper.xmlUserMapperTest.javapom.xml 代理 此处使用的是JDK的动态代理方式,延迟加载使用的cglib动态代理方式 代理分为静态代理和动态代理。此处先不说静态代理,因为…...
网络原理(3)—— 传输层详解
目录 一. 再谈端口号 二. UDP协议(用户数据报协议) 2.1 UDP协议端格式 2.2 UDP报文长度 2.3 UDP校验和 三. TCP协议(传输控制协议) 3.1 TCP协议段格式 3.2 核心机制 3.2.1 确认应答 —— “感知对方是否收到” 3.2.2 超时重传 3.3.3 连接管理 —— 三次握手与四…...
深度学习 Pytorch 神经网络的学习
本节将从梯度下降法向外拓展,介绍更常用的优化算法,实现神经网络的学习和迭代。在本节课结束将完整实现一个神经网络训练的全流程。 对于像神经网络这样的复杂模型,可能会有数百个 w w w的存在,同时如果我们使用的是像交叉熵这样…...
【机器学习】自定义数据集 使用pytorch框架实现逻辑回归并保存模型,然后保存模型后再加载模型进行预测,对预测结果计算精确度和召回率及F1分数
一、使用pytorch框架实现逻辑回归 1. 数据部分: 首先自定义了一个简单的数据集,特征 X 是 100 个随机样本,每个样本一个特征,目标值 y 基于线性关系并添加了噪声。将 numpy 数组转换为 PyTorch 张量,方便后续在模型中…...
深入理解linux中的文件(上)
1.前置知识: (1)文章 内容 属性 (2)访问文件之前,都必须打开它(打开文件,等价于把文件加载到内存中) 如果不打开文件,文件就在磁盘中 (3&…...
分布式微服务系统架构第90集:现代化金融核心系统
#1.1 深化数字化转型,核心面临新挑战 1、架构侧:无法敏捷协同数字金融经营模式转型。 2、需求侧:业务需求传导低效始终困扰金融机构。 3、开发侧:创新产品上市速度低于期望。 4、运维侧:传统面向资源型监控体系难以支撑…...
Vue简介
目录 Vue是什么?为什么要使用Vue?Vue的三种加载方式拓展:什么是渐进式框架? Vue是什么? Vue是一套用于构建用户界面的渐进式 JavaScript (主张最少)框架 ,开发者只需关注视图层。另一方面,当与…...
【Linux】从零开始:编写你的第一个Linux进度条小程序
Linux相关知识点可以通过点击以下链接进行学习一起加油!初识指令指令进阶权限管理yum包管理与vim编辑器GCC/G编译器make与Makefile自动化构建GDB调试器与Git版本控制工具 🌈个人主页:是店小二呀 🌈C语言专栏:C语言 &am…...
FFmpeg工具使用基础
一、FFmpeg工具介绍 FFmpeg命令行工具主要包括以下几个部分: ffmpeg:编解码工具ffprobe:多媒体分析器ffplay:简单的音视频播放器这些工具共同构成了FFmpeg的核心功能,支持各种音视频格式的处理和转换 二、在Ubuntu18.04上安装FFmpeg工具 1、sudo apt-upda…...
数据库管理-第287期 Oracle DB 23.7新特性一览(20250124)
数据库管理287期 2025-01-24 数据库管理-第287期 Oracle DB 23.7新特性一览(20250124)1 AI向量搜索:算术和聚合运算2 更改Compatible至23.6.0,以使用23.6或更高版本中的新AI向量搜索功能3 Cloud Developer包4 DBMS_DEVELOPER.GET_…...
快速提升网站收录:利用网站FAQ页面
本文转自:百万收录网 原文链接:https://www.baiwanshoulu.com/48.html 利用网站FAQ(FrequentlyAskedQuestions,常见问题解答)页面是快速提升网站收录的有效策略之一。以下是一些具体的方法和建议,以帮助你…...
AtCoder Beginner Contest 391(ABCDE)
A - Lucky Direction 翻译: 给你一个字符串 D,代表八个方向(北、东、西、南、东北、西北、东南、西南)之一。方向与其代表字符串之间的对应关系如下。 北: N东: E西: W南: S东…...
解决Django非ORM模型提示初始化request问题
提问 Django在DRF时候自定义显示一些非model的字段提示TypeError: Field.__init__() got an unexpected keyword argument request 解答1 错误提示 TypeError: Field.__init__() got an unexpected keyword argument request 显示在创建序列化器实例时,传递了一个…...
【机器学习】自定义数据集 使用scikit-learn中svm的包实现svm分类
一、支持向量机(support vector machines. ,SVM)概念 1. SVM 绪论 支持向量机(SVM)的核心思想是找到一个最优的超平面,将不同类别的数据点分开。SVM 的关键特点包括: ① 分类与回归: SVM 可以用于分类&a…...
hunyuan 混元学习
使用了5个subset,也是用了text-image和text-video进行训练的 也是进行了复杂的视频选择。同movie gen. 也进行了模型切断,用拉普拉斯算子找到最清晰的一帧作为训练的起始 训练了不同的模型去选择数据,比如用Dover去选择美观度比较好的数据,…...
.Net / C# 繁体中文 与 简体中文 互相转换, 支持地方特色词汇
版本号 Nuget 搜索 “OpenCCNET”, 注意别找错, 好多库的名字都差不多 支持 “繁,简” 的互相转换, 支持多个地区常用词汇的转换, 还支持 日文的新旧转换. OpenCC 在 .Net 中的实现 https://github.com/CosineG/OpenCC.NET <PackageReference Include"OpenCCNET"…...
仿真设计|基于51单片机的温湿度、一氧化碳、甲醛检测报警系统
目录 具体实现功能 设计介绍 51单片机简介 资料内容 仿真实现(protues8.7) 程序(Keil5) 全部内容 资料获取 具体实现功能 (1)温湿度传感器、CO传感器、甲醛传感器实时检测温湿度值、CO值和甲醛值进…...
Vue- 组件通信2
一、props props 是使用频率最高的一种通信方式,常用于:父 ↔ 子 若 父传子:属性值是非函数;若 子传父:属性值是函数。 Props: 指的是传递给子组件的属性。子组件通过 props 接收数据。单向数据流: 数据通过 props…...
春晚舞台上的人形机器人:科技与文化的奇妙融合
文章目录 人形机器人Unitree H1的“硬核”实力传统文化与现代科技的创新融合网友热议与文化共鸣未来展望:科技与文化的更多可能结语 2025 年央视春晚的舞台,无疑是全球华人目光聚焦的焦点。就在这个盛大的舞台上,一场名为《秧BOT》的创意融合…...
向上调整算法(详解)c++
算法流程: 与⽗结点的权值作⽐较,如果⽐它⼤,就与⽗亲交换; 交换完之后,重复 1 操作,直到⽐⽗亲⼩,或者换到根节点的位置 这里为什么插入85完后合法? 我们插入一个85,…...
Python之Excel操作 - 写入数据
我们将使用 openpyxl 库,它是一个功能强大且易于使用的库,专门用于处理 Excel 文件。 1. 安装 openpyxl 首先,你需要安装 openpyxl 库。你可以使用 pip 命令进行安装: pip install openpyxl创建一个文件 example.xlsxÿ…...
MYSQL--一条SQL执行的流程,分析MYSQL的架构
文章目录 第一步建立连接第二部解析 SQL第三步执行 sql预处理优化阶段执行阶段索引下推 执行一条select 语句中间会发生什么? 这个是对 mysql 架构的深入理解。 select * from product where id 1;对于mysql的架构分层: mysql 架构分成了 Server 层和存储引擎层&a…...
【开源免费】基于Vue和SpringBoot的流浪宠物管理系统(附论文)
本文项目编号 T 182 ,文末自助获取源码 \color{red}{T182,文末自助获取源码} T182,文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…...
您与此网站之间建立的连接不安全
网站建立好后,用360浏览器打开后地址栏有一个灰色小锁打着红色叉点击后显示“您与此网站之间建立的连接不安全”“请勿在此网站上输入任何敏感信息(例如密码或信用卡信息),因为攻击者可能会盗取这些信息。” 出现这个提示的主要原…...
kamailio-ACC模块介绍【kamailio6.0. X】
Acc 模块 作者 Jiri Kuthan iptel.org jiriiptel.org Bogdan-Andrei Iancu Voice Sistem SRL bogdanvoice-system.ro Ramona-Elena Modroiu rosdev.ro ramonarosdev.ro 编辑 Bogdan-Andrei Iancu Voice Sistem SRL bogdanvoice-system.ro Sven Knoblich 1&1 Internet …...
图漾相机——Sample_V1示例程序
文章目录 1.SDK支持的平台类型1.1 Windows 平台1.2 Linux平台 2.SDK基本知识2.1 SDK目录结构2.2 设备组件简介2.3 设备组件属性2.4 设备的帧数据管理机制2.5 SDK中的坐标系变换 3.Sample_V1示例程序3.1 DeviceStorage3.2 DumpCalibInfo3.3 NetStatistic3.4 SimpleView_SaveLoad…...
谈谈你所了解的AR技术吧!
深入探讨 AR 技术的原理与应用 在科技飞速发展的今天,AR(增强现实)技术已经悄然改变了我们与周围世界互动的方式。你是否曾想象过如何能够通过手机屏幕与虚拟物体进行实时互动?在这篇文章中,我们将深入探讨AR技术的原…...
C++计算特定随机操作后序列元素乘积的期望
有一个长度为 n n n的序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an。初始序列的所有元素均为 0 0 0。再给定正整数 m m m、 c c c和 ( n − m 1 ) (n-m1) (n−m1)个正整数 b 1 , b 2 , . . . , b n − m 1 b_1,b_2,...,b_{n-m1} b1,b2,...,bn−m1…...
【机器学习理论】朴素贝叶斯网络
基础知识: 先验概率:对某个事件发生的概率的估计。可以是基于历史数据的估计,可以由专家知识得出等等。一般是单独事件概率。 后验概率:指某件事已经发生,计算事情发生是由某个因素引起的概率。一般是一个条件概率。 …...
NPM 使用介绍
NPM 使用介绍 引言 NPM(Node Package Manager)是Node.js生态系统中的一个核心工具,用于管理JavaScript项目的依赖包。无论是开发一个小型脚本还是构建大型应用程序,NPM都能极大地提高开发效率。本文将详细介绍NPM的使用方法,包括安装、配置、依赖管理、包发布等,帮助您…...
langchain 实现多智能体多轮对话
这里写目录标题 工具定义模型选择graph节点函数定义graph 运行 工具定义 import random from typing import Annotated, Literalfrom langchain_core.tools import tool from langchain_core.tools.base import InjectedToolCallId from langgraph.prebuilt import InjectedSt…...
网络攻防实战指北专栏讲解大纲与网络安全法
专栏 本专栏为网络攻防实战指北,大纲如下所示 进度:目前已更完准备篇、HTML基础 计划:所谓基础不牢,地动山摇。所以下一步将持续更新基础篇内容 讲解信息安全时,结合《中华人民共和国网络安全法》(以下简…...
四、jQuery笔记
(一)jQuery概述 jQuery本身是js的一个轻量级的库,封装了一个对象jQuery,jquery的所有语法都在jQuery对象中 浏览器不认识jquery,只渲染html、css和js代码,需要先导入jQuery文件,官网下载即可 jQuery中文说明文档:https://hemin.cn/jq/ (二)jQuery要点 1、jQuery对象 …...
解锁微服务:五大进阶业务场景深度剖析
目录 医疗行业:智能诊疗的加速引擎 电商领域:数据依赖的破局之道 金融行业:运维可观测性的提升之路 物流行业:智慧物流的创新架构 综合业务:服务依赖的优化策略 医疗行业:智能诊疗的加速引擎 在医疗行业迈…...
C++:虚函数与多态性习题2
题目内容: 编写程序,声明抽象基类Shape,由它派生出3个派生类:Circle、Rectangle、Triangle,用虚函数分别计算图形面积,并求它们的和。要求用基类指针数组,使它每一个元素指向一个派生类对象。 …...
开源软件协议介绍
一、可以闭源使用/不具传染性的协议 允许商业使用和分发 1、BSD:详细介绍 2、LGPL许可证:详细介绍 3、MPL2.0:详细介绍 二、具有传染性/使用后需要开源自身软件的协议 不建议商业使用 1、GPL许可证:详细介绍...
MapReduce简单应用(一)——WordCount
目录 1. 执行过程1.1 分割1.2 Map1.3 Combine1.4 Reduce 2. 代码和结果2.1 pom.xml中依赖配置2.2 工具类util2.3 WordCount2.4 结果 参考 1. 执行过程 假设WordCount的两个输入文本text1.txt和text2.txt如下。 Hello World Bye WorldHello Hadoop Bye Hadoop1.1 分割 将每个文…...
【HarmonyOS之旅】基于ArkTS开发(三) -> 兼容JS的类Web开发(三)
目录 1 -> 生命周期 1.1 -> 应用生命周期 1.2 -> 页面生命周期 2 -> 资源限定与访问 2.1 -> 资源限定词 2.2 -> 资源限定词的命名要求 2.3 -> 限定词与设备状态的匹配规则 2.4 -> 引用JS模块内resources资源 3 -> 多语言支持 3.1 -> 定…...
(9) 上:学习与验证 linux 里的 epoll 对象里的 EPOLLIN、 EPOLLHUP 与 EPOLLRDHUP 的不同
(1)经过之前的学习。俺认为结论是这样的,因为三次握手到四次挥手,到 RST 报文,都是 tcp 连接上收到了报文,这都属于读事件。所以: EPOLLIN : 包含了读事件, FIN 报文的正常四次挥手、…...
Avalonia与QtQuick的简单对比
这个是Avalonia开发的示例应用程序(官方入门示例)(Avalonia 11.1.0 .Net 9.0) 刚启动时,内存占用150M左右,稍等一会儿后,内存占用降低到77M左右,CPU占用一直都在,我i9-…...
WebForms DataList 深入解析
WebForms DataList 深入解析 引言 在Web开发领域,控件是构建用户界面(UI)的核心组件。ASP.NET WebForms框架提供了丰富的控件,其中DataList控件是一个灵活且强大的数据绑定控件。本文将深入探讨WebForms DataList控件的功能、用法以及在实际开发中的应用。 DataList控件…...
jetson编译torchvision出现 No such file or directory: ‘:/usr/local/cuda/bin/nvcc‘
文章目录 1. 完整报错2. 解决方法 1. 完整报错 jetson编译torchvision,执行python3 setup.py install --user遇到报错 running build_ext error: [Errno 2] No such file or directory: :/usr/local/cuda/bin/nvcc完整报错信息如下: (pytorch) nxnx-desktop:~/Do…...
《苍穹外卖》项目学习记录-Day10订单状态定时处理
利用Cron表达式生成器生成Cron表达式 1.处理超时订单 查询订单表把超时的订单查询出来,也就是订单的状态为待付款,下单的时间已经超过了15分钟。 //select * from orders where status ? and order_time < (当前时间 - 15分钟) 遍历集合把数据库…...
“新月智能武器系统”CIWS,开启智能武器的新纪元
新月人物传记:人物传记之新月篇-CSDN博客 相关文章链接:星际战争模拟系统:新月的编程之道-CSDN博客 新月智能护甲系统CMIA--未来战场的守护者-CSDN博客 “新月之智”智能战术头盔系统(CITHS)-CSDN博客 目录 智能武…...
FPGA| 使用Quartus II报错Top-level design entity ““ is undefined
1、使用FPGA准备点亮LED测试下板子,发现这个报错Error (12007): Top-level design entity "LEDLED" is undefined 工程如上图 报错如下图 2、分析到原因是因为工程名称和顶层模块里面的module名称不一样导致 解决办法:修改module名称和顶层模…...
如何实现滑动列表功能
文章目录 1 概念介绍2 使用方法3 示例代码 我们在上一章回中介绍了沉浸式状态栏相关的内容,本章回中将介绍SliverList组件.闲话休提,让我们一起Talk Flutter吧。 1 概念介绍 我们在这里介绍的SliverList组件是一种列表类组件,类似我们之前介…...
数据结构:优先级队列—堆
一、优先级队列 1、优先级队列概念 优先级队列,听名字我们就知道他是一种队列,队列在前面我们已经学习过了,它是一种先进先出的数据结构,但是在特殊的情况下,我们我们队列中元素是带有一定优先级的,它需要…...
SpringCloud系列教程:微服务的未来(十八)雪崩问题、服务保护方案、Sentinel快速入门
前言 在分布式系统中,雪崩效应(Avalanche Effect)是一种常见的故障现象,通常发生在系统中某个组件出现故障时,导致其他组件级联失败,最终引发整个系统的崩溃。为了有效应对雪崩效应,服务保护方…...