AcWing 786. 第k个数
原题链接
简单
作者:
bruce
,
2021-01-23 11:49:37
,
所有人可见
,
阅读 239
#include<iostream>
#include<vector>
using namespace std;
const int N = 100010;
int a[N], n, k;
int quick_sort(int l, int r, int k)
{
if(r == l) return a[l];
int i = l-1, j = r+1;
int x = a[(l+r)/2];
while(i<j)
{
while(a[++i] < x);
while(a[--j] > x);
if(i<j) swap(a[i], a[j]);
}
int s1 = j-l+1; // 在答案范围内 右端点 到 左端点的距离长度
if(s1 >=k) return quick_sort(l, j, k); // 如果k不超过这个长度,说明在和这个区间继续查找
else return quick_sort(j+1, r, k-s1);
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
scanf("%d", &a[i]);
}
cout<<quick_sort(0, n-1, k)<<endl;
}