在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内

[问答题]

在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。

代码受虐者

10G的整数找出中位数，限制内存2G，假设数都是int型占4B，2G内存一次性能读入5亿个int，10G整数int总共有25亿个int，分5次读入？nono，这样只能判断某位数是否存在。延申：找第k个数，可以先分批读入排序，再多路归并，得到有序序列找第k个数。

但找中位数可以有另一个思路，不用全部排序，4B * 512MB = 2G，可以把int的取值范围32bit位的空间分为512MB个取值范围，即内存中0~512M的位置表示，对每个取值范围内的数进行统计，遍历一次后知道每个范围内出现了多少个数，便可以得出中位数在那个范围内出现，再对这个范围内出现的整数进行排序，找到中数。

发表于 2021-04-28 12:30:25 回复(0)

短尾矮袋鼠

10G个乱序整数，求中位数：基于桶排序的思想。每次读入1G的文件，根据整数的最高8bit写入到文件中，分到2^8=256个桶里，同时在内存中记录每个桶的count。根据每个桶的数量确定中位数在哪个桶里。假设数据分布比较均匀，每个桶的大小大概在10G/256=40MB, 可以读入内存。用O(NlogN)的排序方法即可得到结果。

发表于 2017-09-17 19:47:21 回复(0)