P1923. 模板题_求第 k 小的数

发表于 2023-10-05 更新于 2023-10-25 分类于洛谷阅读次数： Waline：本文字数： 314 阅读时长 ≈ 1 分钟

考点

排序

题解

#include <bits/stdc++.h>

using namespace std;

const int LEN = 5e6 + 10;

int K, arr[LEN];

int k_th(int arr[], int len)
{
    if (len <= 1)
        return arr[0];
    int i = 0, j = 0, k = len, pivot = arr[rand() % len];
    while (i < k)
    {
        if (arr[i] < pivot)
            swap(arr[i++], arr[j++]);
        else if (arr[i] > pivot)
            swap(arr[i], arr[--k]);
        else
            ++i;
    }
    if (K < j)
        return k_th(arr, j);
    else if (K >= k)
    {
        K -= k;
        return k_th(arr + k, len - k);
    }
    else
        return pivot;
}

int main()
{
    //这行必须加，加快cin的读取速度
    ios::sync_with_stdio(false);
    int n;
    cin >> n >> K;
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    cout << k_th(arr, n);
    return 0;
}