STL中nth_element的用法
2024-08-30 01:35:28
nth_element函数原型有四个,详细我就不一一累赘了,我们就用最普通的用法寻找第k位置的元素。
函数用法为:nth_element(first,kth,end)。
first,last 第一个和最后一个迭代器,也可以直接用数组的位置。
kth,要定位的第k个元素,能对它进行随机访问.
将第k_th元素放到它该放的位置上,左边元素都小于等于它,右边元素都大于等于它.
例如:
vector<int> a();
for(int i = ; i < ; i++)
a[i] = i+;
random_shuffle(a.begin(),a.end());
for(int i = ; i < ; i++)
cout << a[i] << " ";
cout << endl; nth_element(a.begin(),a.begin()+,a.end());
cout << *(a.begin()+) << endl; for(int i = ; i < ; i++)
cout << a[i] << " ";
cout << endl;
结果为:
可以发现函数只是把kth的元素放在了正确位置,对其他元素并没有排序,所以可以利用这个函数快速定位第k个元素,当然,这个函数也支持你直接写比较函数,此处不再累赘因为ACM中基本不会用到。
那么为什么要选择这个函数呢,这就和复杂度有关了,nth_element的空间复杂度为O(1),在数据量大的时候时间复杂度为O(n),数据少的情况最坏为O(n^2),因为函数原理是随机访问,但实际运用过程中,基本都会是O(n)的时间复杂度。所以说是非常迅速的。
最新文章
- UIImageView
- js部分总结
- WebForm中搭配母版页和用户控件页时候的事件加载顺序
- 你所不知道的Python奇技淫巧
- Vue.js学习 Item14 – 过滤器与自定义过滤器
- Cordova 3.0 Plugin 安装 及";git"; command line tool is not installed
- ZCTF-final-restaurant1
- list与数组转换
- Thymeleaf3语法详解和实战
- 关于DOM的事件操作
- MGR实现分析 - 成员管理与故障恢复实现
- CentOS 7 建立svn仓库 远程连接
- flex布局下, 内容改变 不重新渲染问题
- Java 增强 for 循环
- UI 交互
- MongoDB的分布式部署
- 7.Python使用pandans遇到的坑
- Silverlight &; Blend动画设计系列十二:三角函数(Trigonometry)动画之自由旋转(Free-form rotation)
- cacti监控多个mysql端口
- web.xml文件的作用及基本配置
热门文章
- ubuntu 开机进入grub rescue> 解决办法(nvme固态硬盘)
- .NET中的缓存
- 第 10 篇:小细节 Markdown 文章自动生成目录,提升阅读体验
- CentOS 7 中配置Firewall规则
- idea中pom如何加载jar包依赖
- mybatis多表查询之多对多关系查询的实现-xml方式
- 集合系列 List(二):ArrayList
- rabbitmq集群操作与启停
- tesseract4.0:win10 +x64+vs2015 源码安装(ViewerDebugging)安装记录
- Spring学习之旅(十二)--持久化框架