题解：P1923 求第 k 小的数

· · 题解

题解：P1923 【深基9.例4】求第 k 小的数

题目大意

一个大小为 n(1 \le n \le 5 \times 10^6) 的数组 a，输出数组中第 k 小的数（最小的数是第 0 小）。

分析

本题可以使用分治算法。分治，顾名思义就是“分而治之”，也就是把一个大问题分解成规模更小但本质相同的问题，再用同样的方法解决，再把小问题的解合并，就是大问题的解。

这一题，我们可以随便选择一个数，并将数组分为三部分：比它小的数，这个数本身，和比它大的数。然后再判断第 k 小的数位于哪个部分，再在这个部分中继续用同样的方法查找，直到得出答案为止。平均时间复杂度可以达到 O(n)。

注意最小的数是第 0 小，所以分治之前 k 要加一。且数据范围比较大，需要用 scanf 和 printf 快速读入输出。

代码

可能这样说比较抽象，那就结合代码理解吧！

#include <iostream>
#include <cstdio> // 快速读入输出头文件
#include <vector> // 动态数组头文件
using namespace std;

long long n, k; // 有自定义函数，使用全局变量
long long a[5000005];

void dfs(long long l, long long r) // 自定义函数
{
    if (l > r) // 如果 l > r
    {
        return; //  直接返回
    }
    long long num = a[l];
    // 随便选一个数，为了写代码方便就选第 1 个数
    vector <long long> minn, maxn;
    // 存储比这个数大或小的数的数组，因为大小未知，所以使用动态数组
    for (long long i = l + 1; i <= r; ++i) // 遍历这一段区间
    {
        if (a[i] < num) // 将数字存入数组
        {
            minn.push_back(a[i]);
        }
        else
        {
            maxn.push_back(a[i]);
        }
    }
    for (long long i = l; i < l + minn.size(); ++i) 
    {
        a[i] = minn[i - l];
    }
    // 改变数组中数的位置，使得数组分为三部分：比 num 小的数，num 本身，和比 num 大的数
    // 注意 for 循环的范围
    a[l + minn.size()] = num;
    for (long long i = l + minn.size() + 1; i <= r; ++i)
    {
        a[i] = maxn[i - l - minn.size() - 1];
    }
    if (k < minn.size() + 1) // 分类讨论，答案在左半边
    { 
        dfs(l, l + minn.size() - 1); // 递归
    }
    else if (k == minn.size() + 1) // 答案正好是 num
    {
        printf("%lld", num); // 输出答案，注意使用 printf 更快
        exit(0); // 直接退出程序
    }
    else // 答案在右半边
    { 
        k -= minn.size() + 1; // 改变 k 的值
        dfs(l + minn.size() + 1, r); // 递归
    }
}

int main()
{
    scanf("%lld %lld", &n, &k); // 输入，注意使用 scanf 更快
    for (long long i = 1; i <= n; ++i)
    {
        scanf("%lld", &a[i]);
    }
    k += 1; // 题目说最小的数是第 0 小
    dfs(1, n); // 搜索并递归

    return 0; // 完结撒花！！！！！
}

这道题还可以直接用 sort 排序，或者用题面提到的 nth_element 函数，但本题的考点是分治算法，这里就不赘述其他方法了。

:::info[你可以] 点个赞再走吧！ :::

:::warning[注意] 不要抄题解，会棕名的！ :::