STL中nth_element的用法

  1. 云栖社区>
  2. 博客列表>
  3. 正文

STL中nth_element的用法

xenny 2018-08-05 11:20:00 浏览192 评论0

摘要: nth_element函数原型有四个,详细我就不一一累赘了,我们就用最普通的用法寻找第k位置的元素。 函数用法为:nth_element(first,kth,end)。 first,last 第一个和最后一个迭代器,也可以直接用数组的位置。

nth_element函数原型有四个,详细我就不一一累赘了,我们就用最普通的用法寻找第k位置的元素。

函数用法为:nth_element(first,kth,end)。

first,last 第一个和最后一个迭代器,也可以直接用数组的位置。
kth,要定位的第k个元素,能对它进行随机访问.

将第k_th元素放到它该放的位置上,左边元素都小于等于它,右边元素都大于等于它.

例如:

 1     vector<int> a(9);
 2     for(int i = 0; i < 9; i++)
 3         a[i] = i+1;
 4     random_shuffle(a.begin(),a.end());
 5     for(int i = 0; i < 9; i++)
 6         cout << a[i] << " ";
 7     cout << endl;
 8 
 9     nth_element(a.begin(),a.begin()+4,a.end());
10     cout << *(a.begin()+4) << endl;
11     
12     for(int i = 0; i < 9; i++)
13         cout << a[i] << " ";
14     cout << endl;

结果为:

可以发现函数只是把kth的元素放在了正确位置,对其他元素并没有排序,所以可以利用这个函数快速定位第k个元素,当然,这个函数也支持你直接写比较函数,此处不再累赘因为ACM中基本不会用到。

那么为什么要选择这个函数呢,这就和复杂度有关了,nth_element的空间复杂度为O(1),在数据量大的时候时间复杂度为O(n),数据少的情况最坏为O(n^2),因为函数原理是随机访问,但实际运用过程中,基本都会是O(n)的时间复杂度。所以说是非常迅速的。

 

用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

xenny
文章26篇 | 关注7
关注
是解决用户结构化数据搜索需求的托管服务,支持数据结构、搜索排序、数据处理自由定制。 为您的网... 查看详情
云数据库PPAS版,是阿里云与EnterpriseDB公司合作基于PostgreSQL高度兼... 查看详情
PostgreSQL被业界誉为“最先进的开源数据库”,面向企业复杂SQL处理的OLTP在线事... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航