如何从5亿个数中找出中位数？
文档摘要
如何从 5 亿个数中找出中位数？ 题目描述 从 5 亿个数中找出中位数。数据排序后，位置在最中间的数就是中位数。当样本数为奇数时，中位数为 第 个数；当样本数为偶数时，中位数为 第 个数与第 个数的均值。 解答思路 如果这道题没有内存大小限制，则可以把所有数读到内存中排序后找出中位数。但是最好的排序算法的时间复杂度都为 。这里使用其他方法。 方法一：双堆法 维护两个堆，一个大顶堆，一个小顶堆。大顶堆中最大的数小于等于小顶堆中最小的数；保证这两个堆中的元素个数的差不超过 1。 若数据总数为偶数，当这两个堆建好之后，中位数就是这两个堆顶元素的平均值。当数据总数为奇数时，根据两个堆的大小，中位数一定在数据多的堆的堆顶。 见 LeetCode No.295：https://leetcode.
评论区
(0)
U