大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。
瑶瑶的第K大
Time Limit: 10000/5000MS (Java/Others)Memory Limit: 512000/256000KB (Java/Others)
SubmitStatisticNext Problem
Problem Description
一天，萌萌的妹子–瑶瑶(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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118702.html原文链接：https://javaforall.net
