大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
一天,萌萌的妹子–瑶瑶(tsyao)非常无聊,就来找你玩。但是你们都不知道玩什么。。。尴尬了一阵子,机智的瑶瑶就提议:“这样吧,你说N个整数xi,然后在任意说一个数字k,我可以高速地说出这些数字里面第 k 大的数字。”
Input
第1行 两个整数N, K以空格隔开;
第2行 有N个整数(可出现相同数字,均为随机生成),相同以空格隔开。
0 < n ≤ 5*10^6 , 0 < k ≤ n
1 ≤ xi ≤ 10^8
Output
输出第 k 大的数字。
Sample Input
5 2
5 4 1 3 1
Sample Output
4
Hint
如2,2,1中三个数字中第一大数字为2,第二大数字也为2,第三大数字为1 。
闲来无聊,静静心,刷刷水题,突然想起快排的实现过程还不懂,于是就找到了这个题,专研了快排,也算懂个所以然了!
只是这个题做得纠结啊,卡超时卡得太紧了,还得优化输入,无奈啊!!
AC代码例如以下:
#include<iostream> #include<cstring> #include<cstdio> #define M 6000010 using namespace std; int num[M]; int input() { int ans=0; char a; while((a=getchar())<'0'||a>'9'); ans=a-'0'; while((a=getchar())>='0'&&a<='9') { ans=ans*10+a-'0'; } return ans; } int qsort(int l,int r,int k) { if(l==r) return num[l]; int i,j,a; a=num[l];i=l;j=r; while(i<j) { while(i<j&&num[j]<=a) j--; if(i<j) num[i++]=num[j]; while(i<j&&num[i]>=a) i++; if(i<j) num[j--]=num[i]; } num[i]=a; if(i==k) return num[i]; else if(i>k) return qsort(l,i-1,k); else return qsort(i+1,r,k); } int main() { int i,j; int n,k; n=input();k=input(); for(i=1;i<=n;i++) num[i]=input(); int ans=qsort(1,n,k); printf("%d\n",ans); return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118702.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...