题目描述

blablabla

样例

//快速选择 时间复杂度O(n)
#include <iostream>
using namespace std;

const int N = 1E6+10;
int q[N], n, k;

int quick_sort(int l, int r, int k){
    if(l == r) return q[l];
    int x = q[l], i = l - 1, j = r + 1;
    while(i < j){
        while(q[++i] < x);
        while(q[--j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    int sl = j - l + 1;
    if(k <= sl) return quick_sort(l, j, k);
    return quick_sort(j+1, r, k-sl);
}

int main(){

    cin >> n >> k;
    for(int i = 0; i < n; ++i) cin>>q[i];

    cout<<quick_sort(0, n-1, k)<<endl;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla