100亿个整数，内存足够，如何找到中位数？内存不足，如何找到

[问答题]

100亿个整数，内存足够，如何找到中位数？内存不足，如何找到中位数？

查看答案及解析

陈木木

内存足够的情况：可以使用类似quick sort的思想进行，均摊复杂度为O(n)，算法思想如下：
• 随机选取一个元素，将比它小的元素放在它左边，比它大的元素放在右边
• 如果它恰好在中位数的位置，那么它就是中位数，可以直接返回
• 如果小于它的数超过一半，那么中位数一定在左半边，递归到左边处理
• 否则，中位数一定在右半边，根据左半边的元素个数计算出中位数是右半边的第几大，然后递归到右半边处理
内存不足的情况：
方法：分法
思路：一个重要的线索是，这些数都是整数。整数就有范围了，32位系统中就是[-2^32, 2^32- 1]，有了范围我们就可以对这个范围进行二分，然后找有多少个数⼩于Mid,多少数大于mid，然后递归，和基于quicksort思想的第k大方法类似
方法二：分桶法思路：化大为小，把所有数划分到各个小区间，把每个数映射到对应的区间里，对每个区间中数的个数进行计数，数一遍各个区间，看看中位数落在哪个区间，若够小，使用基于内存的算法，否则继续划分

编辑于 2015-05-18 13:06:54 回复(3)

simmon_hu

1.内存足够时：快排

2.内存不足时：分桶法：化大为小，把所有数划分到各个小区间，把每个数映射到对应的区间里，对每个区间中数的个数进行计数，数一遍各个区间，看看中位数落在哪个区间，若够小，使用基于内存的算法，否则继续划分

发表于 2015-06-11 19:45:37 回复(0)

得得小泽

1 快速排序 2 分桶

发表于 2015-07-17 14:59:49 回复(0)

cancer大魔王

中位数定义：数字排序之后，位于中间的那个数。比如将100亿个数字进行排序，排序之后，位于第50亿个位置的那个数就是中位数。

①内存够：内存够还慌什么啊，直接把100亿个全部排序了，你用冒泡都可以...然后找到中间那个就可以了。但是你以为面试官会给你内存？？

②内存不够：题目说是整数，我们认为是带符号的int,所以4字节，占32位。

假设100亿个数字保存在一个大文件中，依次读一部分文件到内存(不超过内存的限制)，将每个数字用二进制表示，比较二进制的最高位(第32位，符号位，0是正，1是负)，如果数字的最高位为0，则将这个数字写入 file_0文件中；如果最高位为 1，则将该数字写入file_1文件中。

从而将100亿个数字分成了两个文件，假设 file_0文件中有 60亿个数字，file_1文件中有 40亿个数字。那么中位数就在 file_0 文件中，并且是 file_0 文件中所有数字排序之后的第 10亿个数字。（file_1中的数都是负数，file_0中的数都是正数，也即这里一共只有40亿个负数，那么排序之后的第50亿个数一定位于file_0中）

现在，我们只需要处理 file_0 文件了（不需要再考虑file_1文件）。对于 file_0 文件，同样采取上面的措施处理：将file_0文件依次读一部分到内存(不超内存限制)，将每个数字用二进制表示，比较二进制的次高位（第31位），如果数字的次高位为0，写入file_0_0文件中；如果次高位为1，写入file_0_1文件中。

现假设 file_0_0文件中有30亿个数字，file_0_1中也有30亿个数字，则中位数就是：file_0_0文件中的数字从小到大排序之后的第10亿个数字。

抛弃file_0_1文件，继续对 file_0_0文件根据次次高位(第30位) 划分，假设此次划分的两个文件为：file_0_0_0中有5亿个数字，file_0_0_1中有25亿个数字，那么中位数就是 file_0_0_1文件中的所有数字排序之后的第 5亿个数。

按照上述思路，直到划分的文件可直接加载进内存时，就可以直接对数字进行快速排序，找出中位数了。

编辑于 2017-08-21 10:49:02 回复(10)

势在必得

假设整数是32位的，根据每个整数二进制前的5位，可以划分为32个不同的桶，如果某个桶的个数在内存中放不下，则继续划分，知道内存可以放下为止；然后统计每个桶中的数的个数，就可以中位数一定出现在哪个桶中，而且知道是该桶中第几大数，因为桶的划分是根据二进制前缀来进行划分的，桶之间是排好序的。

发表于 2015-08-04 11:08:59 回复(0)

亮亮666

<p>内存足够采用直接查找法，先排序，再找到序号是中间的数</p>

发表于 2020-04-30 05:53:59 回复(0)

秋招补招春招求战友

内存足够的时候，为什么不用堆排序

发表于 2018-08-02 22:25:37 回复(0)

牛客548682号

使用bit-map来做，考虑无符号整形，最大为2的32次方，给予每一位2个bit，00表示为出现，01表示出现1次，10表示出现多次（之后不在出现变化），那么所需的内存为2的32次方*2bit等于1GB左右的内存来表示所有数，顺序便利100亿个数，那么一个位数组的每一位都可能从00变为01，再从01变为10，之后过滤调位数组中表示为00的位置，取其中间下标即为中位数。

发表于 2018-04-29 00:06:20 回复(0)