首页 > 代码库 > 求第k大数
求第k大数
题意：输入n个整数和一个正整数k(k>=1&&k<=n)，输出这些数从小到大排序后的第k个(例如，k=1就是最小值)。n<=10^7。
分析：由于n比较大如果先排序后求解，那时间复杂度有点高了n*log(n)，然后hash的话数组开不了，用什么方法求解呢？我这里给出一种用快速排序的方法解决，当然这就需要对快速排序的原理理解了，自己百度吧！
代码实现：
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;int k;int a[10000005];int partition(int l,int r,int a[]){ int key=a[l],index=l; for(int i=l+1;i<r;i++) if(a[i]<key) { index++; swap(a[index],a[i]); } swap(a[l],a[index]); return index;}void quickSort(int l, int r, int a[]){ if(l<r) { int mid = partition(l,r,a); if(k>=l&&k<=mid-1) quickSort(l,mid-1,a); else quickSort(mid+1,r,a); }}int main(){ int i,n; while(scanf("%d%d",&n,&k)!=EOF) { k--; for(i=0; i<n; i++) scanf("%d",&a[i]); quickSort(0,n,a); for(i=0;i<n-1;i++) printf("%d ",a[i]); printf("%d\n",a[n-1]); printf("%d\n",a[k]); } return 0;}
求第k大数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。