本文主要是介绍第k大的数(快速排序的划分过程)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
瑶瑶的第K大
Time Limit: 10000/5000MS (Java/Others) Memory Limit: 512000/256000KB (Java/Others)
Submit Statistic Next 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
Submit Statistic
卡我输入简直桑心病狂...
#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)return l;int q=rand()%(r-l+1)+l;swap(A[r],A[q]);int x=A[r];int t=l-1;rep(i,l,r-1){if(A[i]<=x){++t;swap(A[t],A[i]);}}swap(A[t+1],A[r]);return t+1;
}
int quick_select(int l,int r,int k)
{if(l==r)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-1,k);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<<1)+(x<<3)+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大的数(快速排序的划分过程)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
