c++的stl库之nth_element函数

nth_element函数

好久没用补题了,今天去牛客补了几道水题,其中一道是要在无序表中快速找到第k小的数,这道题数据太大了,用sort()和partial_sort() 都会超时,垃圾的我一开始就是直接用sort写的,不出意料的超时了,接着又尝试了桶排序,自己又tle了,然后无聊的翻了下群,发现有个人说nth_element函数可以快速做完这道题,顿时感觉孤陋寡闻了,马上百度了下这个函数,交了一波,ac了。事后,还是记下笔记,写一下这个函数的用法,免得下次又忘了。

 

nth_element()

  • 头文件:#include<algorithm>
  • 格式:nth_element(begin,nth,end,compare)
  • 期望复杂度:O(N)

例子:数组a在第1-n位置有元素,现求第k大的数

 

nth_element(a+1,a+k,a+n+1,cmp)

 

注意,代码中的cmp可以删去,如果不使用cmp函数,默认是“<”

 

原理:

在当前区间[L,R]上,找一个基准位置mid

通过线性的扫描交换,类似快排的一部分,

使得[L,mid)的元素都比mid小,(mid,R]的元素都比mid大

此时mid上的元素就是第mid小的

然后判断k在哪半边,继续递归处理

所以这样就达到了期望的O(N)复杂度

代码:

#include<bits/stdc++.h>
using namespace std;
int a[5000006];
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
int main()
{
    
    int t,n,k;
    t=read();
    while(t--)
    {
        n=read();
        k=read();
        k--;
        for(int i=0;i<n;i++)
            a[i]=read();
        nth_element(a,a+k,a+n);
        cout<<a[k]<<"\n";
    }
}

 

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像