在寻找 n 个元素中第 k 小元素问题中,如使用快速排序算法思想,运用分治算法对 n 个元素进行划分,应如何选择划分基准?下面( ) 答案解释最合理。
随机选择一个元素作为划分基准
取子序列的第一个元素作为划分基准
用中位数的中位数方法寻找划分基准
以上皆可行。但不同方法,算法复杂度上界可能不同
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题