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

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),它是快速排序算法的一个变种。其主要步骤如下:

  1. 选择支点:从序列中选择一个元素作为支点(pivot)。

  2. 分区操作:将序列分为两部分:

    • 小于等于支点的元素放在支点的左边。

    • 大于支点的元素放在支点的右边。

  3. 递归处理

    • 如果支点的位置恰好是 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 标准库中提供的一个算法&#xff0c;位于 <algorithm> 头文件中&#xff0c;用于部分排序序列。它的主要功能是将…...

DNS缓存详解(DNS Cache Detailed Explanation)

DNS缓存详解 清空DNS缓存可以让网页访问更快捷。本文将从什么是DNS缓存、为什么清空DNS缓存、如何清空DNS缓存、清空DNS缓存存在的问题四个方面详细阐述DNS缓存清空的相关知识。 一、什么是DNS缓存 1、DNS缓存的定义&#xff1a; DNS缓存是域名系统服务在遇到DNS查询时自动…...

课设:【ID0022】火车票售票管理系统(前端)

技术栈&#xff1a;Java&#xff0c;JavaSwing&#xff0c;MySQL 数据库表数量&#xff1a;12个 1.功能描述 管理员功能 管理员是系统的高级用户&#xff0c;拥有对整个系统的全面管理权限。管理员的功能模块包括以下六个方面&#xff1a; 对用户管理增删查改 对售票员…...

Ruby 类和对象

Ruby 类和对象 引言 在软件开发中,类和对象是面向对象编程(OOP)的核心概念。Ruby 作为一种动态、解释型编程语言,也以简洁的方式支持面向对象编程。本文将深入探讨 Ruby 中的类和对象,包括它们的定义、创建、使用以及一些高级特性。 类与对象的定义 类 在 Ruby 中,类…...

Java基础知识总结(三十八)--读取数据

使用Reader体系&#xff0c;读取一个文本文件中的数据。返回 -1 &#xff0c;标志读到结尾。 import java.io.*; class { public static void main(String[] args) throws IOException { /* 创建可以读取文本文件的流对象&#xff0c;让创建好的流对象和指定的文件相关联。…...

交错定理和切比雪夫节点的联系与区别

1. 交错定理 交错定理是切比雪夫逼近理论的核心内容&#xff0c;描述在区间[a,b]上&#xff0c;一个函数 f ( x ) f(x) f(x)的最佳一致逼近多项式 P n ( x ) P_n(x) Pn​(x)的特性。定理内容如下&#xff1a; 设 f ( x ) f(x) f(x)是区间[a,b]上的连续函数&#xff0c; P n ( …...

大数据相关职位介绍之三(数据挖掘,数据安全 ,数据合规师,首席数据官,数据科学家 )

大数据相关职位介绍之三&#xff08;数据挖掘&#xff0c;数据安全 &#xff0c;数据合规师&#xff0c;首席数据官&#xff0c;数据科学家 &#xff09; 文章目录 大数据相关职位介绍之三&#xff08;数据挖掘&#xff0c;数据安全 &#xff0c;数据合规师&#xff0c;首席数据…...

GitHub Actions定时任务配置完全指南:从Cron语法到实战示例

你好&#xff0c;我是悦创。 博客网站&#xff1a;https://blog.bornforthis.cn/ 本教程将详细讲解如何在GitHub Actions中配置定时任务&#xff08;Scheduled Tasks&#xff09;&#xff0c;帮助你掌握 Cron 表达式的编写规则和实际应用场景。 一、定时任务基础配置 1.1 核…...

Van-Nav:新年,将自己学习的项目地址统一整理搭建自己的私人导航站,供自己后续查阅使用,做技术的同学应该都有一个自己网站的梦想

嗨&#xff0c;大家好&#xff0c;我是小华同学&#xff0c;关注我们获得“最新、最全、最优质”开源项目和高效工作学习方法 Van-Nav是一个基于Vue.js开发的导航组件库&#xff0c;它提供了多种预设的样式和灵活的配置选项&#xff0c;使得开发者可以轻松地定制出符合项目需求…...

Easy系列PLC尺寸测量功能块ST代码(激光微距仪应用)

激光微距仪可以测量短距离内的产品尺寸,产品规格书的测量 精度可以到0.001mm。具体需要看不同的型号。 1、激光微距仪 2、尺寸测量应用 下面我们以测量高度为例子,设计一个高度测量功能块,同时给出测量数据和合格不合格指标。 3、高度测量功能块 4、复位完成信号 5、功能…...

Manacher 最长回文子串

方法&#xff1a;求字符串的 #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单片机开发:独立键盘实验

实验目的&#xff1a;按下键盘1时&#xff0c;点亮LED灯1。 键盘原理图如下图所示&#xff0c;可见&#xff0c;由于接GND&#xff0c;当键盘按下时&#xff0c;P3相应的端口为低电平。 键盘按下时会出现抖动&#xff0c;时间通常为5-10ms&#xff0c;代码中通过延时函数delay…...

组件框架漏洞

一.基础概念 1.组件 定义&#xff1a;组件是软件开发中具有特定功能或特性的可重用部件或模块&#xff0c;能独立使用或集成到更大系统。 类型 前端 UI 组件&#xff1a;像按钮、下拉菜单、导航栏等&#xff0c;负责构建用户界面&#xff0c;提升用户交互体验。例如在电商 AP…...

OFDM系统仿真

1️⃣ OFDM的原理 1.1 介绍 OFDM是一种多载波调制技术&#xff0c;将输入数据分配到多个子载波上&#xff0c;每个子载波上可以独立使用 QAM、PSK 等传统调制技术进行调制。这些子载波之间互相正交&#xff0c;从而可以有效利用频谱并减少干扰。 1.2 OFDM的核心 多载波调制…...

基于单片机的盲人智能水杯系统(论文+源码)

1 总体方案设计 本次基于单片机的盲人智能水杯设计&#xff0c;采用的是DS18B20实现杯中水温的检测&#xff0c;采用HX711及应力片实现杯中水里的检测&#xff0c;采用DS1302实现时钟计时功能&#xff0c;采用TTS语音模块实现语音播报的功能&#xff0c;并结合STC89C52单片机作…...

安心即美的生活方式

如果你的心是安定的&#xff0c;那么&#xff0c;外界也就安静了。就像陶渊明说的&#xff1a;心远地自偏。不是走到偏远无人的边荒才能得到片刻清净&#xff0c;不需要使用洪荒之力去挣脱生活的枷锁&#xff0c;这是陶渊明式的中国知识分子的雅量。如果你自己是好的男人或女人…...

安卓(android)订餐菜单【Android移动开发基础案例教程(第2版)黑马程序员】

一、实验目的&#xff08;如果代码有错漏&#xff0c;可查看源码&#xff09; 1.掌握Activity生命周的每个方法。 2.掌握Activity的创建、配置、启动和关闭。 3.掌握Intent和IntentFilter的使用。 4.掌握Activity之间的跳转方式、任务栈和四种启动模式。 5.掌握在Activity中添加…...

【cocos creator】【模拟经营】餐厅经营demo

下载&#xff1a;【cocos creator】模拟经营餐厅经营...

前端 | 深入理解Promise

1. 引言 JavaScript 是一种单线程语言&#xff0c;这意味着它一次仅能执行一个任务。为了处理异步操作&#xff0c;JavaScript 提供了回调函数&#xff0c;但是随着项目处理并发任务的增加&#xff0c;回调地狱 (Callback Hell) 使异步代码很难维护。为此&#xff0c;ES6带来了…...

Visual Studio Code修改terminal字体

个人博客地址&#xff1a;Visual Studio Code修改terminal字体 | 一张假钞的真实世界 默认打开中断后字体显示如下&#xff1a; 打开设置&#xff0c;搜索配置项terminal.integrated.fontFamily&#xff0c;修改配置为monospace。修改后效果如下&#xff1a;...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...