问题遇到的现象和发生背景
第 k 大的整数**
求 n 个整数中第 k(1≤k≤n) 大的整数。
输入格式
n 和 k
n 个整数
输出格式
第 k 大的整数
输入样例
10 3
2 5 -1 9 25 0 12 4 -7 12
输出样例
12
用代码块功能插入代码,请勿粘贴截图
#include <iostream>
#include <algorithm>
using namespace std;
int quickselect(int num[],int start,int end,int k)
{
int low=start;
int high=end;
int tmp=num[low];
while(low<high)
{
while(low<high&&num[high]<=tmp) high--;
num[low]=num[high];
while(low<high&&num[low]>=tmp) low++;
num[high]=num[low];
}
num[high]=tmp;
if(high==k-1) return tmp;//当前的枢轴点就是第K大的数
else if(high>k-1) return quickselect(num,start,end-1,k);
else return quickselect(num,start+1,end,k);
}
int main()
{
int n,k,e;
cin>>n>>k;
int a[100001];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
e=quickselect(a,0,n-1,k);
cout<<e<<endl;
return 0;
}