题解 | #第k轻的牛牛#

知识点

排序，性质

思路

在快速排序的过程中，每次会找到一个基准值，将大于基准值的数放在左边，小于基准值的数放在右边，这个过程实际上就确定了基准值的排名！此时如果基准值的排名小于 ，那么说明第 大的水晶在基准值的右边，否则就在左边，递归这个过程就可以找到第 大的水晶！ 实际上这个过程是先用 的时间复杂度将区间分成两个部分，然后再到其中一个部分去寻找答案，在最坏情况下如果每次基准值都将区间分成大小为L和N-L的区间，然后再到 的区间里去寻找那么总复杂度可以达到O(N*N)。但是如果每次随机选择基准值，那么期望时间复杂度为O(N)

核心代码

int kth (int l, int r, int k)//第k大，在此题中可以转换为n-k大的数，即第k小
{
    int p = rand() % (r - l + 1) + l;//随机一个基准值
    swap(a[p], a[l]);
    int lt = l + 1, rt = r;
    while (lt < rt) {
        while (lt < rt && a[lt] > a[l])    ++lt;
        while (lt < rt && a[rt] <= a[l])    --rt;
        if (lt > rt)    break;
        swap(a[lt], a[rt]);
    }
    --lt;
    swap(a[l], a[lt]);
    int rk = lt - l + 1;
    if (rk == k)    return a[lt];
    if (k < rk)    return kth(l, lt - 1, k);
    return kth(lt + 1, r, k - rk);
}

本文转自天大算协公众号