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> 头文件中,用于部分排序序列。它的主要功能是将…...
DNS缓存详解(DNS Cache Detailed Explanation)
DNS缓存详解 清空DNS缓存可以让网页访问更快捷。本文将从什么是DNS缓存、为什么清空DNS缓存、如何清空DNS缓存、清空DNS缓存存在的问题四个方面详细阐述DNS缓存清空的相关知识。 一、什么是DNS缓存 1、DNS缓存的定义: DNS缓存是域名系统服务在遇到DNS查询时自动…...
课设:【ID0022】火车票售票管理系统(前端)
技术栈:Java,JavaSwing,MySQL 数据库表数量:12个 1.功能描述 管理员功能 管理员是系统的高级用户,拥有对整个系统的全面管理权限。管理员的功能模块包括以下六个方面: 对用户管理增删查改 对售票员…...
Ruby 类和对象
Ruby 类和对象 引言 在软件开发中,类和对象是面向对象编程(OOP)的核心概念。Ruby 作为一种动态、解释型编程语言,也以简洁的方式支持面向对象编程。本文将深入探讨 Ruby 中的类和对象,包括它们的定义、创建、使用以及一些高级特性。 类与对象的定义 类 在 Ruby 中,类…...
Java基础知识总结(三十八)--读取数据
使用Reader体系,读取一个文本文件中的数据。返回 -1 ,标志读到结尾。 import java.io.*; class { public static void main(String[] args) throws IOException { /* 创建可以读取文本文件的流对象,让创建好的流对象和指定的文件相关联。…...
交错定理和切比雪夫节点的联系与区别
1. 交错定理 交错定理是切比雪夫逼近理论的核心内容,描述在区间[a,b]上,一个函数 f ( x ) f(x) f(x)的最佳一致逼近多项式 P n ( x ) P_n(x) Pn(x)的特性。定理内容如下: 设 f ( x ) f(x) f(x)是区间[a,b]上的连续函数, P n ( …...
大数据相关职位介绍之三(数据挖掘,数据安全 ,数据合规师,首席数据官,数据科学家 )
大数据相关职位介绍之三(数据挖掘,数据安全 ,数据合规师,首席数据官,数据科学家 ) 文章目录 大数据相关职位介绍之三(数据挖掘,数据安全 ,数据合规师,首席数据…...
GitHub Actions定时任务配置完全指南:从Cron语法到实战示例
你好,我是悦创。 博客网站:https://blog.bornforthis.cn/ 本教程将详细讲解如何在GitHub Actions中配置定时任务(Scheduled Tasks),帮助你掌握 Cron 表达式的编写规则和实际应用场景。 一、定时任务基础配置 1.1 核…...
Van-Nav:新年,将自己学习的项目地址统一整理搭建自己的私人导航站,供自己后续查阅使用,做技术的同学应该都有一个自己网站的梦想
嗨,大家好,我是小华同学,关注我们获得“最新、最全、最优质”开源项目和高效工作学习方法 Van-Nav是一个基于Vue.js开发的导航组件库,它提供了多种预设的样式和灵活的配置选项,使得开发者可以轻松地定制出符合项目需求…...
Easy系列PLC尺寸测量功能块ST代码(激光微距仪应用)
激光微距仪可以测量短距离内的产品尺寸,产品规格书的测量 精度可以到0.001mm。具体需要看不同的型号。 1、激光微距仪 2、尺寸测量应用 下面我们以测量高度为例子,设计一个高度测量功能块,同时给出测量数据和合格不合格指标。 3、高度测量功能块 4、复位完成信号 5、功能…...
Manacher 最长回文子串
方法:求字符串的 #include<bits/stdc.h> using namespace std; using lllong long; const int N1e69; char s[N]; int p[N];int main() {cin>>s1;int nstrlen(s1);s[0]^;s[2*n2]$; for(int i2*n1;i>1;i--){s[i](i&1)?#:s[i>>1];//右移表示…...
51单片机开发:独立键盘实验
实验目的:按下键盘1时,点亮LED灯1。 键盘原理图如下图所示,可见,由于接GND,当键盘按下时,P3相应的端口为低电平。 键盘按下时会出现抖动,时间通常为5-10ms,代码中通过延时函数delay…...
组件框架漏洞
一.基础概念 1.组件 定义:组件是软件开发中具有特定功能或特性的可重用部件或模块,能独立使用或集成到更大系统。 类型 前端 UI 组件:像按钮、下拉菜单、导航栏等,负责构建用户界面,提升用户交互体验。例如在电商 AP…...
OFDM系统仿真
1️⃣ OFDM的原理 1.1 介绍 OFDM是一种多载波调制技术,将输入数据分配到多个子载波上,每个子载波上可以独立使用 QAM、PSK 等传统调制技术进行调制。这些子载波之间互相正交,从而可以有效利用频谱并减少干扰。 1.2 OFDM的核心 多载波调制…...
基于单片机的盲人智能水杯系统(论文+源码)
1 总体方案设计 本次基于单片机的盲人智能水杯设计,采用的是DS18B20实现杯中水温的检测,采用HX711及应力片实现杯中水里的检测,采用DS1302实现时钟计时功能,采用TTS语音模块实现语音播报的功能,并结合STC89C52单片机作…...
安心即美的生活方式
如果你的心是安定的,那么,外界也就安静了。就像陶渊明说的:心远地自偏。不是走到偏远无人的边荒才能得到片刻清净,不需要使用洪荒之力去挣脱生活的枷锁,这是陶渊明式的中国知识分子的雅量。如果你自己是好的男人或女人…...
安卓(android)订餐菜单【Android移动开发基础案例教程(第2版)黑马程序员】
一、实验目的(如果代码有错漏,可查看源码) 1.掌握Activity生命周的每个方法。 2.掌握Activity的创建、配置、启动和关闭。 3.掌握Intent和IntentFilter的使用。 4.掌握Activity之间的跳转方式、任务栈和四种启动模式。 5.掌握在Activity中添加…...
【cocos creator】【模拟经营】餐厅经营demo
下载:【cocos creator】模拟经营餐厅经营...
前端 | 深入理解Promise
1. 引言 JavaScript 是一种单线程语言,这意味着它一次仅能执行一个任务。为了处理异步操作,JavaScript 提供了回调函数,但是随着项目处理并发任务的增加,回调地狱 (Callback Hell) 使异步代码很难维护。为此,ES6带来了…...
Visual Studio Code修改terminal字体
个人博客地址:Visual Studio Code修改terminal字体 | 一张假钞的真实世界 默认打开中断后字体显示如下: 打开设置,搜索配置项terminal.integrated.fontFamily,修改配置为monospace。修改后效果如下:...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...
人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型
在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重,适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解,并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...
云安全与网络安全:核心区别与协同作用解析
在数字化转型的浪潮中,云安全与网络安全作为信息安全的两大支柱,常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异,并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全:聚焦于保…...
Java后端检查空条件查询
通过抛出运行异常:throw new RuntimeException("请输入查询条件!");BranchWarehouseServiceImpl.java // 查询试剂交易(入库/出库)记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...
门静脉高压——表现
一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构:由肠系膜上静脉和脾静脉汇合构成,是肝脏血液供应的主要来源。淤血后果:门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血,引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...
