最坏复杂度为线性时间的序列第k大查找算法

 逛知乎看到有人提到算法导论上有最坏复杂度也能保证为线性的找序列第k大就去学了一波

虽然貌似没啥用,而且有重复元素还会假掉,nth_element真香(

参考自《算法导论》P123

将n个元素划分成floor(n/5)组,每组五个元素,然后剩下的数单独为一组

找到总共ceil(n/5)组的中位数(最后一组如果有偶数个取小的),然后递归调用这个方法找到这些中位数的中位数

按照找到的这个中位数的中位数划分为高区和低区,设找到的数为第x大,那么k=x当前数就是答案,如果k<x就递归低区,k>x就递归高区

证明略,建议直接看算法导论

评论

此博客中的热门博文

min-max反演