快速选择
这里可以直接用快排, 然后输出arr[k-1] 即可,时间复杂度为 nlogn
故这里采用快速选择 , 其时间复杂度为 On
#include<iostream>
using namespace std;
constexpr int N = 1e+5 + 10;
int n,k;
int arr[N];
void fun(int l, int r, int pos) // 采用的是快排的模版
{
if(l >= r) return;
int mid = l + r >> 1;
int base = arr[mid];
int i = l - 1, j = r + 1;
while(j > i)
{
do ++i;while(arr[i] < base);
do --j;while(arr[j] > base);
if(j > i) swap(arr[i],arr[j]);
} //到这一步都跟快排一样
int sl = j - l + 1; // 计算出分界点包括本身的左边有多少个带点
if(sl >= pos) fun(l,j,pos); // 若要求的位置<= sl,说明在左边区间,只要排序左边区间即可,同理只需要排序右边区间
else fun(j+1,r, pos - sl); // 排序右边区间注意此时的参3要更新!!!
}
int main()
{
cin >> n >> k;
for(int i = 0; i < n; ++i) cin >> arr[i];
fun(0,n-1);
cout << arr[k-1];
}
注意事项
用到的模板是快排,在快排的基础上递归的写法上改变了,变成了现在的快选。 这里需要注意的一个问题就是如果题目要求的第 k 小的数位于当前分界点的右边的时候,要更新递归方程的参3,整个数据中的第k小,如果在右边那就是右边区间的 第 k - sl 个,sl 为分界点左边数的个数。