标签 双堆法 下的文章

题目描述从 5 亿个数中找出中位数。数据排序后,位置在最中间的数就是中位数。当样本数为奇数时,中位数为 第 (N+1)/2 个数;当样本数为偶数时,中位数为 第 N/2 个数与第 1+N/2 个数的均值。解答思路如果这道题没有内存大小限制,则可以把所有数读到内存中排序后找出中位数。但是最好的排序算法的时间复杂度都为 O(NlogN) 。这里使用其他方法。方法一:双堆法维护两个堆,一个大顶堆,一个小顶堆。大顶堆中最大的数小于等于小顶堆中最小的数;保证这两个堆中的元素个数的差不超过 1。

- 阅读剩余部分 -