题目描述

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。

样例

输入：5 3
2 4 1 5 3
输出：3

算法1

(暴力排序) $O(nlogn)$

先排序，在输出

时间复杂度 $O(nlogn)$

参考文献 无

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int n,k,a[N];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    cout<<a[k-1]<<endl;
    return 0;
}

算法2

(快速选择) $O(n)$

上网搜

时间复杂度 $O(n)$

参考文献 无

C++ 代码

上网搜！