nth_element      复杂度O(n)

nth_element是<algorithm>里面的一个库函数

可以用来方便的求出第n大的数  

用法

nth_element(a+L, a+n,a+R )          范围是  [ L , R )

nth_element并不会为整个数列排序  

而是调用nth_element(a+L, a+n,a+R ) 方法之后呢

第n个位置（L是第0个位置 从L开始数的第n个）的数  前边都是比他小的  后边都是比他大的

（将比这个元素小的元素都排在这个元素之前，比这个元素大的元素都排在这个元素之后）

举个栗子

这段代码的执行结果呢是

从0开始数  0，1，2，3，4，5   a [ 5 ]的位置上的数  前边的都比他小  后边的都比他大

这个函数就是这么一个效果

那么我们怎么用这个函数找数列中第k大的数呢？

既然是第k大  那么比他还大的数就有k-1个  应该排在他后边

那么他就是就从后往前数的第k个数   也就是正着数的第n-k个数

那么我们就用   nth_element(a+0 , a+n-k , a+n ) 

用数组的写法


//使用nth_element求数组中第k大的数
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[10]={9,8,7,6,5,4,3,2,1,0};
    int k;
    while(~scanf("%d",&k)){
        nth_element(a+0,a+10-k,a+10);
        printf("数列中第%d大的数是  %d\n",k,a[10-k]);
    }
}

执行结果

使用容器的写法

//使用nth_element求数组中第k大的数
#include<bits/stdc++.h>
using namespace std;
int main(){
    vector<int>a;
    for(int i=0;i<10;i++){
        a.push_back(i);
    }
    int k;
    scanf("%d",&k);
    nth_element(a.begin(),a.begin()+a.size()-k,a.end());
    printf("数列中第%d大的数是  %d\n",k,a[a.size()-k]);
}

执行结果