AcWing 786. 第k个数
原题链接
简单
作者:
月下邂逅
,
2024-04-17 16:59:06
,
所有人可见
,
阅读 1
第k个数
#include<iostream>
using namespace std;
const int N=1000010;
int arr[N];
void quick_sort(int arr[],int l,int r)
{
//l>=r时说明所有数据都已经安排完了,可以返回
if(l>=r)return ;
//i和j会先进行一次++和--再操作,num取中间数的值,取两边的值可能会超出内存限制
int i=l-1,j=r+1,num=arr[l+r>>1];
while(i<j)
{
do i++;while(arr[i]<num);
do j--;while(arr[j]>num);
//i和j相等时可以不交换
if(i<j) swap(arr[i],arr[j]);
}
//以j划分num不能为arr[r],以i划分不能选择arr[l]
quick_sort(arr,l,j);
quick_sort(arr,j+1,r);
}
int main()
{
int n,k;
//scanf和printf的速度远远快于cin和cout
scanf("%d",&n);
scanf("%d",&k);
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
//快速排序
quick_sort(arr,0,n-1);
printf("%d ",arr[k-1]);
return 0;
}