AcWing 786. 第k个数

# 第 k 个数 - 快速选择

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, k;
int q[N];

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;
}

// 如果用快排做的话 时间复杂度是 nlog(n)

// 所以用快速选择做 时间复杂度是 O(n)
// 因为快速选择 1. k <= s[l], 递归左边
//              2. k > s[l], 递归右边 然后继续
// n + n/2 + n/4 + ...
// = n(1 + 1/2 + 1/4 + 1/8 + ...)
// = n(<= 2)
// <= 2n
// 所以是 O(n)

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, k;
int q[N];

int quick_sort(int l, int r, int k){
    //在 c++ 里，如果局部变量和全局变量重名的话，我们会优先使用局部变量
    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);
}
//这边直接return int 就不用写输出了

int main(){
    cin >> n >> k;
    
    for(int i = 0; i < n; i++) cin >> q[i];
    
    cout << quick_sort(0, n - 1, k) << endl;
//这边直接return int 就不用写输出了
    
    return 0;
}