【模板】第 K 大数
发布时间:2020-12-14 04:17:40 所属栏目:大数据 来源:网络整理
导读:题目:给定一个序列,求其第 K 大的数是多少。 时间复杂度 (O(n)) 代码如下: #include bits/stdc++.husing namespace std;const int maxn=5e6+10;inline int read(){ int x=0,f=1;char ch; do{ch=getchar();if(ch==‘-‘)f=-1;}while(!isdigit(ch)); do{x
题目:给定一个序列,求其第 K 大的数是多少。 时间复杂度(O(n)) 代码如下: #include <bits/stdc++.h> using namespace std; const int maxn=5e6+10; inline int read(){ int x=0,f=1;char ch; do{ch=getchar();if(ch==‘-‘)f=-1;}while(!isdigit(ch)); do{x=x*10+ch-‘0‘;ch=getchar();}while(isdigit(ch)); return f*x; } int n,k,a[maxn]; int k_th(int l,int r,int k){ if(l==r)return a[l]; int tmp=a[l],i=l,j=r; while(i<j){ while(i<j&&a[j]>=tmp)j--; while(i<j&&a[i]<=tmp)i++; if(i<j)swap(a[i],a[j]); } swap(a[l],a[i]); if(r-i>=k)return k_th(i+1,r,k); else return k_th(l,i,k-r+i); } int main(){ n=read(),k=read(); for(int i=1;i<=n;i++)a[i]=read(); printf("%dn",k_th(1,n,k)); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |