硬盘中有 10T 的 int 数据，从中找出中位数、众数

问题描述

一台 PC 机，硬盘上有 10G 个 int，内存有 2G，分析硬盘中的数据，找到第 K 大、中位数、众数、平均数。

先看一下众数：如果众数的个数过半，则可以 O(n)复杂度扫描一遍得到。

ma=a[0]
cnt=0
for i in a:
   if i==ma:
       cnt+=1
   else:
       ma=i
       cnt-=1
print(ma)

如果寻找中位数，可以使用二分法，在 0 到2^32之间进行二分，统计小于 x 的数字的个数。
空间复杂度为 O(1)，时间复杂度为扫描硬盘 32 次。

如果求大量数据的平均数，直接把所有的数据进行加和放在 int 里面会导致溢出，所以需要使用大整数运算。使用 int64 作为当前变量，使用一个List<int> a作为当前的总和，a 就相当于一个2^30进制的大整数。最终需要进行大整数除法。

利用外排序的方法，进行排序 ,然后再去找中位数。

外排序就是由于数据量太大不能一次性加载到内存，所以需要先暂时用外存储器（硬盘）将数据存起来，然后依次读入一部分数据到内存，排序之后，生成临时文件存储到硬盘，最后再对这些临时文件进行一个归并，得到最后的排序结果（在合并的过程中虽然不需要多大内存，但是会产生频繁的 IO 操作，频繁的读磁盘和写磁盘）

经典的求 topK，建立一个大小 K 的堆，不停地往堆里面塞入数据，弹出其中的最小值。如果 K 比较小，这种算法可以在内存里面进行，如果 K 非常大，在此题中，至少需要把 5G 的数据放在堆中，这是不可接受的。

但是经过修改之后，也是能做到的，在内存里面建立一个 1G 大小的最大堆，可以求出第 1G 大的数据。然后第二遍扫描的时候大于这个 1G 大的数据就完全忽略掉。这样就能够得到第 2G 大的数据......

先求第 1G 大，然后利用该元素求第 2G 大，然后利用第 2G 大，求第 3G 大...当然这样的话虽不需排序，但是磁盘操作会比较多，具体还需要分析下与外排序的效率哪个的磁盘 IO 会比较多

建立一个 1g 个整数的最大值堆，如果元素小于最大值则入堆，这样可以得到第 1g 大的那个元素然后利用这个元素，重新建一次堆，这次入堆的条件还要加上大于这个第 1g 大的元素，这样建完堆可以得到第 2g 大的那个 ...

先计算中位数的 top16bit 是什么，top16 bit 总共有 65536 种情况，扫描一遍就能确定中位数的 top16 位是什么（记为 x），然后第二遍扫描只处理 top16 位等于 x 的数据，从中便能找到中位数。

一个整数假设是 32 位无符号数第一次扫描把 0~2^32-1 分成 2^16 个区间，记录每个区间的整数数目找出中位数具体所在区间 65536i~65536(i+1)-1 第二次扫描则可找出具体中位数数值

第一次扫描已经找出中位数具体所在区间 65536i~65536(i+1)-1 然后第二次扫描再统计在该区间内每个数出现的次数，就可以了

使用逐次求精的算法。第一次求出比较粗略的桶，可以确定中位数一定位于这个桶内。然后第二遍扫描，只处理落在这个桶里面的数据，找出更精细的数据个数。

使用 0/1 表示某个 int 是否存在，int 是 32 位，最多有 2^32 种 int，所以使用 2G 空间可以存储下来所有数字是否出现。
但是为了统计中位数，需要进行计数，把 2^32 平均分成 4 份进行处理。
最多需要扫描四遍，如果数据范围更小，则存在更优的复杂度。