当前位置: 首页 > 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;...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

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

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

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...