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。修改后效果如下:...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...
