题解 | #第k轻的牛牛#

第k轻的牛牛

https://www.nowcoder.com/practice/7676478b46794456b145e8e48b0e2763

知识点

排序,性质

思路

在快速排序的过程中,每次会找到一个基准值,将大于基准值的数放在左边,小于基准值的数放在右边,这个过程实际上就确定了基准值的排名!此时如果基准值的排名小于 ,那么说明第 大的水晶在基准值的右边,否则就在左边,递归这个过程就可以找到第 大的水晶! 实际上这个过程是先用 的时间复杂度将区间分成两个部分,然后再到其中一个部分去寻找答案,在最坏情况下如果每次基准值都将区间分成大小为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);
}

本文转自天大算协公众号

全部评论

相关推荐

10-11 15:42
皖西学院 Java
青鱼LINK:我硕士,也是java0面试,吾道不孤
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务