题解 P1368 【均分纸牌（加强版）】

· · 题解

关于这题的做法，相信前面的题解和刘汝佳的蓝书已经解释得很清楚了，这里我来介绍一下书上没有提到的线性时间复杂度查找中位数的做法。

对于一个无序的长度为n的数组，如何在O(n)的时间复杂度内求得它的中位数？

朴素的解法是将数组排序，然后答案就是a[n/2]，这样的方法固然可行，但是时间复杂度是O(n*log n)的，对于较大的n来说可能无法承受。

考虑我们是如何用快速排序算法进行排序的。首先选取一个基准元X，然后对基准元左边和右边依此遍历，使得x的左端都是比x小的数，x的右端都是比x大的数，然后对这两端分别进行排序。

然而我们发现，如果我们只需要求得中位数，可以根据x左右元素的个数，来判断选择对哪边进行一次查找中位数的操作。

注意，只需要对一边进行查找操作！

如果x左右元素个数相等，那真是非常的幸运，恭喜你，x就是这个数组的中位数。

如果哪边包含了a+n/2这个位置，就只对那边进行查找中位数操作。

容易证明，这种方法的期望时间复杂度是O(n)。

但是在某些特殊情况下，这种算法的时间复杂度不是O(n)的，比如最坏情况是数组完全是逆序的，这个时候时间复杂度是O(n*log n)，但是我们可以通过一定的随机化防止人工设计数据卡掉程序。

给一个查找中位数的函数的代码，请看注释：

const int maxn=10000010;//数据范围
int n,a[maxn];//n和a的定义如上
int qsort(int a[],int l,int r)//查找中位数的函数
{
    int i=l,j=r,x=a[(l+r)>>1],y;//x是基准元
    while(i<=j)
    {
        while(a[i]<x)i++;
        while(a[j]>x)j--;//调整左右使得x左边全是比x小的数
        if(i<=j)swap(a[i++],a[j--]);
    }
    if(i-1==n>>1)return a[n>>1];//如果正好在中间，恭喜你，这就是中位数
    if(i<=n>>1&&i<=r)return qsort(a,i,r);
    if(j>=n>>1&&l<=j)return qsort(a,l,j);//分别讨论，只需要对其中的一边进行查找操作
    return -1;//错误返回代码
}

本人亲测，对于n=1e8范围的数据，这个代码只用跑不到1s，而C++ STD sort则跑了10多s。好吧笔者的机子比较慢的。

洛谷评测线性方法384ms，O(n*log n)方法1488ms。