题解 | #第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);
}
本文转自天大算协公众号