AcWing 786. 第k个数
原题链接
简单
作者:
bruce
,
2021-01-23 00:07:38
,
所有人可见
,
阅读 357
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
/**
* 使用快速选择排序来求解第k个数字是多少
* 思路就是先选择一个数字x,左边的数字都小于这个x且个数大于等于k的话,那么说明第k个数字在
* 左边的区间,否则右边的数字大于等于这个数x且个数大于k,那么在右边
*/
const int N = 100010;
int a[N], n, k;
int quick_sort(int l, int r, int k)
{
if (l == r)
return a[l];
int i = l - 1, j = r + 1;
int x = a[l]; // 中枢值
while (i < j)
{
while (a[++i] < x) ;
while (a[--j] > x) ;
if(i < j) swap(a[i], a[j]);
}
int sl = j - l + 1;
if(sl >= k) return quick_sort(l, j, k);
else return quick_sort(j+1, r, k-sl);
}
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
cout << quick_sort(0, n - 1, k) << endl;
return 0;
}