顽强拼搏的小硕

本题考察分治算法的运用。这题容易踩的一个坑就是，容易想到直接排序后直接打印第 $k$ 个元素，但是在数据范围中却是会超时的。桶排序开不下空间桶，用映射优化又会超时，即使是目前最快的排序算法——tim sort也会超时两个点，所以明显这道题正解不是排序。

思路一

在学习快速排序的时候，我们知道一个基准数的性质，那就是基准数左边的数一定小于基准数，基准数右边的数一定大于基准数，利用这个性质，我们可以在快排的时候避免排序多余的部分，只需要排序包含第 $k$ 小的元素的区间即可。也就是说，在我们进行分治的时候，我们只需要治理含第 $k$ 小的元素的区间。为此，我们可以利用快速排序的分治思想来解决这道题。

这还是一道卡其他语言空间的题目，即使用了正确的算法，给定两倍空间，Python和Java还是会MLE

C语言实现（代码改于洛谷P1923题解）

#include <stdio.h>
#include <stdlib.h>
void swap(long long *a, long long *b) {
    long long tmp = *a;
    *a = *b;
    *b = tmp;
}
long long x[5000005], k;
void qselect(long long l, long long r) {
    long long i = l, j = r, mid = x[(l + r) / 2];
    do {
        while (x[j] > mid)
            j--;
        while (x[i] < mid)
            i++;
        if (i <= j) {
            swap(x + i, x + j);
            i++;
            j--;
        }
    } while (i <= j);
    // 快排后数组被划分为三块： l<=j<=i<=r
    if (k <= j)
        qselect(l, j); // 在左区间只需要搜左区间
    else if (i <= k)
        qselect(i, r); // 在右区间只需要搜右区间
    else             // 如果在中间区间直接输出
    {
        printf("%lld", x[j + 1]);
        exit(0);
    }
}
signed main() {
    long long n;
    scanf("%lld", &n);
    for (long long i = 0; i < n; i++)
        scanf("%lld", &x[i]);
    scanf("%lld", &k);
    qselect(0, n - 1);
    return 0;
}

C++ 实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;  // 别名

void quick_select(vector<i64> &arr, const i64 &l, const i64 &r, const i64 &k) {
    auto i = l, j = r, mid = arr[(l + r) >> 1];
    while (i <= j) {
        while (arr[j] > mid)
            j--;
        while (arr[i] < mid)
            i++;
        if (i <= j)
            swap(arr[i++], arr[j--]);
    }
    if(k <= j)
        quick_select(arr, l, j, k);
    else if(i <= k)
        quick_select(arr, i, r, k);
    else {
        cout << arr[j + 1];
        exit(0);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 n;
    cin >> n;
    vector<i64> arr(n);
    for (auto &&i: arr)
        cin >> i;
    i64 k;
    cin >> k;
    quick_select(arr, 0, n - 1, k);
    return 0;
}

思路二

STL 大法好，STL 给我们提高了一个 $O(n)$ 求区间第 $k$ 小元素的函数，我们直接使用它即可（注意，你需要打开 O2 优化）

#include <bits/stdc++.h>
using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector arr(n, 0ll);
    for (auto &&i : arr)
        cin >> i;
    int k;
    cin >> k;
    // C++20之前的 nth_element 用法如下
    // nth_element(arr.begin(), arr.begin() + k, arr.end());
    ranges::nth_element(arr, arr.begin() + k);
    cout << arr[k];
    return 0;
}