jelly_can的专栏

转载 线性时间的中位数查找算法

原帖链接一、以期望线性时间做选择一般来说，中位数的查找算法都是基于先排序，后找中间位置的数字的算法，但是因为线性时间排序所收到的限制比较大，而如果使用基于比较的排序，时间复杂度将至少为O(nlogn)，如何以线性时间完成中位数或者数组中第N大元素的查找呢？快速排序算法在每一次局部递归后都保证某个元素左侧的元素都比他小，右侧的元素都比她大，因此，可以利用这个思路快