nth_element()函数的应用
发布时间
阅读量：
阅读量
在2021年济南站的D题中,题目要求计算一个序列的中位数值。没有想到更高效的方法,于是调用了sort函数,并计算其时间复杂度为O(n log n)。后来发现有人使用了nth_element函数实现了同样的功能,并且时间复杂度更低。学习了一下并加以应用。该函数的作用是将第K小的元素放置在指定的位置上,其中K是一个相对位置索引值,因此需要注意数组下标的处理方法。具体的实现方式为: nth_element(a + l, a + k + l - 1, a + r, cmp);其中cmp是用来定义排序比较的方式。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[]={0,-3,7,-9,10,-10};//五个元素
nth_element(a+1,a+3,a+5+1);//a+1,a+3+1-1,a+r
for(int i=1;i<=5;i++){
cout<<a[i]<<" ";
}
cout<<endl;
} 结果：-9 -10 -3 7 10//可以看到第三小的数-3被转移到了第3个，但其他的仍乱序。全部评论 (0)
还没有任何评论哟~