首页 > 代码库 > 第k大的数(快速排序的划分过程)
第k大的数(快速排序的划分过程)
瑶瑶的第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 。
Source
tsyao
Manager
tsyao
SubmitStatistic
卡我输入简直桑心病狂...
/*
* this code is made by NULL
* Problem: 1099
* Verdict: Accepted
* Submission Date: 2014-09-12 17:35:54
* Time: 3224MS
* Memory: 21212KB
*/
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<vector>
#include<set>
#include<ctime>
#include<map>
#include<stack>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define CLR(a,x) memset(a,x,sizeof(a))
const int maxn=5e6+5;
int A[maxn],n,k;
int Partition(int l,int r)
{
if(l==r-1)return l;
int q=rand()%(r-l-1)+l;
swap(A[r-1],A[q]);
int x=A[r-1];
int t=l-1;
rep(i,l,r-2){
if(A[i]<=x){
++t;
swap(A[t],A[i]);
}
}
swap(A[t+1],A[r-1]);
return t+1;
}
int quick_select(int l,int r,int k)
{
if(l==r-1)return A[l];
int q=Partition(l,r);
int Left=q-l+1;
if(k==Left)return A[q];
else if(k<Left)return quick_select(l,q,k);
else return quick_select(q+1,r,k-Left);
}
char ch;
void read(int &x)
{
ch=x=0;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
while(~scanf("%d%d",&n,&k))
{
srand(time(NULL));
k=n-k+1;
rep(i,1,n)read(A[i]);
printf("%d\n",quick_select(1,n,k));
}
return 0;
}第k大的数(快速排序的划分过程)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。