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

· · 题解

P.S.$ $2020.5.30$更新了 $bug

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

题外话

我瞄了一眼题解区，几乎都在用快读+sort刷水题。

无优化对比

效果对比显然

下面进入正题：

我们发现这道题的题目要求是sort所有功能的一部分，而且数据及范围是O（nlogn）所不能及的，这就是我们当初学快排之前接触快排原理的原因了。

早知今日 做题 惨死被卡常，何必当初 学习 只了解皮毛？

思路

  1. 类似快速排序，我们先随机找到一个值

  2. 然后扫一遍整个序列，这样可以统计出比他大的数的个数X和比他小的数的个数Y，以及跟他相等的个数Z

  3. （1）如果K<=Y,那我们不用管后半部分，第K小元素一定在这些数当中，递归即可

（2）如果Y<k<=Y+Z,那这个元素就是第K小

（3）如果Y+Z<k，那我们不用管前半部分，第K小元素一定在后面的那些数中，我们要找那X个数中的第K-(Y+Z)个元素

  1. 由于值是随机选取的，我们可以认为他把原数列分成差不多相等的两部分

    时间复杂度

    ### 代码
#include <bits/stdc++.h>
using namespace std;
int a[5000005],k,n;//数组记得多开一点
//内联函数要慎重，NOIP选手用递归时就不要开了，养成习惯从平时做起
void mysort(int l,int r)
{//看上去while很多，并且要递归好多次，实际上指针只扫了一遍，所以时间复杂度是O(n)的！
    int lmid=l,rmid=r,mid=a[(l+r)/2];//mid可以随机抽取，这里为了更养眼
    while(lmid<=rmid)
    {
        while(a[rmid]>mid)
            rmid--;
        while(a[lmid]<mid)
            lmid++;
        if(lmid<=rmid)
        {
            swap(a[lmid],a[rmid]);
            lmid++;rmid--;
        }
    }
    //这样就把这些数分成三部分(l <-> rmid <-> lmid <-> r),下面分治
    if(k<=rmid)mysort(l,rmid);
    else if(lmid<=k)mysort(lmid,r);
    else
    {
        cout<<a[rmid+1]<<"\n";
        return;
    }
}
int main()
{
    scanf("%d%d",&n,&k);
//  为显示本算法的高效性，于是不加快读了
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    random_shuffle(a,a+n);
    mysort(0,n-1);//注意是 0 -> (n-1)
    return 0;
}