链接:https://ac.nowcoder.com/acm/contest/21763/1005
来源:牛客网
题目描述
给你一个长度为n的序列,求序列中第k小数的多少。
输入描述:
多组输入,第一行读入一个整数T表示有T组数据。
每组数据占两行,第一行为两个整数n,k,表示数列长度和k。
第二行为n个用空格隔开的整数。
输出描述:
对于每组数据,输出它的第k小数是多少。
每组数据之间用空格隔开
示例1
输入
2
5 2
1 4 2 3 4
3 3
3 2 1
输出
2
3
code
#include<iostream>
#include<cstring>
using namespace std;
const int N=5000010;
int a[N];
int fast_sort(int a[],int l,int r,int k)
{
if(l>=r)return a[l];
else
{
int i =l-1, j =r+1;
int mid=(l+r)/2;
int x=a[mid];
while(i<j)
{
//退出时i=j
do i++;while(a[i]<x);
do j--;while(a[j]>x);
if(i<j)swap(a[i],a[j]);
}
//退出时,i=j,并且a[j]=x=a[i],前面的数据都是小于x,则l到j的数小于等于x,有j-l+1个数
if(j-l+1>=k)return fast_sort(a,l,j,k);//在前面找
else return fast_sort(a,j+1, r, k-(j-l+1));//在后面找剩余大的数
}
}
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x * f;
}
int main()
{
int t;
cin>>t;
while(t--)
{
memset(a,0,sizeof a);
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
{
a[i] =read();
}
int res=fast_sort(a,0,n-1,k);
cout<<res<<endl;
}
return 0;
}