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

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...