挑战程序员同学，如何只用2GB内存从20/40/80亿个整数中找到出现次数最多的数？

这是一个典型的空间复杂度与时间复杂度的trade-off问题。只有2GB内存，需要在超大数据集中找到出现次数最多的元素，难度较大。一般来说,有两种思路：

1、外部排序法:

将数据分成多个块，每个块加载到内存中进行排序，排序后将出现次数最多的topk元素存入外部存储。全部块处理完成后，再从外部存储的topk元素中找到全局的topk。

这种方法时间复杂度较高，需要多轮I/O和外部排序，但可以在有限内存下完成。空间复杂度只需要O(M)，M为topk元素数。

2、桶排序法:

将元素值范围划分为N个桶，每个桶统计对应范围内元素出现次数，存储为桶的计数器。遍历数据将每个元素放入对应桶中，仅更新桶计数器。最后遍历桶计数器找到出现次数最多的前k个桶，再在这k个桶内找出全局出现次数最多的元素。

这种方法可以最大限度利用内存，在一轮遍历中完成排序，时间复杂度较低。但空间复杂度为O(N)，N为桶数，可能超出2GB限制。

综合两种方法，这里推荐一种时间与空间复杂度兼顾的算法：

1、根据数据集大小和内存大小估计一个适当的桶数N，使单个桶占用内存不超过2GB/N，同时N也不致太大。

2、遍历数据集，将每个元素放入对应桶，更新桶计数器。如果某个桶占用内存超过限制，则将该桶中的数据外部排序，清空内存。

3、所有数据处理完成后，对未超出内存限制的桶进行内部topk查找。对超出内存限制的桶，加载外部文件找到topk元素。

4、从所有桶的topk元素中查找全局的topk数。

这种方法可以在有限内存下处理大规模数据，时间和空间复杂度都得到了较好的trade-off，既利用了内存也利用了外部存储，总体效率较高。相比外部排序法,可以减少I/O与外部处理的轮数；相比全桶排序，也不会由于内存不足而导致卡顿和效率低下。这应该是解决此类问题的一个较好思路。

一、用4字节表示的整数个数为2^32≈40亿，而用2字节表示的无符号整数个数为2^16≈6万。

二、2G=2^31B≈20亿字节。

三、要找出出现次数最多的数，则应记录每个数出现的次数，最快的方法是在内存中将每个数出现的次数记录下来，记录的方法则是内存地址对应数，相应地址的内存单元记录次数，但2G内存以字节为单位仅能记录20亿个数，且每个数出现的次数大于255将会出现溢出风险。因此，这一方案不可取。

四、这样只能将每个次出现的次数记录在磁盘上。这样在磁盘上建一个16G的文件，每4字节对应一个整数，可对应40亿个整数，并用于记录相应整数的出现的次数。

1、将文件初始化。

2、依次读取数据，并用无符号整数记录在磁盘文件中，如出现溢出，则该数为次数最多的数。

3、从文件中读取各数出现的次数，用一个变量A记录最高次数，再用一个变量B记录最高次数出现的数据个数，要用个文件依次记录最高次数出现的数。当最高次数增加时，A+1，B置1，文件中写入该数，同次数的数出现时，B+1，文件相应位置写入该数，直到全部读完。

这样根本不需2G内存。

需求：

使用2G的内存，找出80亿个数字中出现最多的数字。

假设：

1. 整数为4字节（2^32=4G），即最大40多亿。
   
2. 所有的数字有80亿个。
3. 所有数字在硬盘中，本身不会占用内存。
   
4. 所用内存为2G多一些，例如有限的变量。但多出的内存和2G相比可以忽略不计。
   

设计：

1. 80亿的计数可以用4字节保存（2^32=4G）。因为如果计数超过一半，则表明该数字一定是出现最多的。
   
2. 2G的内存约可以保存5亿多数字的计数（2G/4=512M）。
   

也就是说，将2G的内存分成单位为4字节的数组，可以一次获得0∼5亿多之间出现最多的数字。

步骤：

1. 顺序扫描80亿个数字，忽略0∼512M之外的数字，每个数字N的出现个数累加存放在第N个数组元素中。最后将最出现最多的数字及其次数保存起来，出现并列第一时，只保存第一个数字。如果过程中某数字出现个数超过40亿，则直接结束。
   
2. 再次扫描所有数字，此次忽略512M∼1G之外的数字。每个数字N的出现个数累加存放在第N-512M个数组元素中。本轮所获得的数字的出现个数和第一轮结果比较，保存较大的那个。
   
3. 由于整数取值范围为4G，所以最多扫描8次后即可获得最终结果。
   

问题：

如果整数长度为8字节，则需要扫描约300多亿次（2^64/512M=2^40）。所以此算法并不适用于8字节的整数。

讨论：

当数字足够多，且数字取值范围足够大时，以有限内存获取出现次数最多的数字几乎是不可能的。因为数字的取值范围极大，且数字极多，任何哈希或其它分片的算法都有可能出现极端情况，导致分片数据过多而无法一次性导入内存计算。除非我们预先知道部分数字规律，否则考虑到效率，应该只会要求得到近似结果。

2g内存不是重点，80亿数字和取值范围才是重要的：

1. 80亿的数字至少需要加载一遍，才知道有哪些数据

2. 如果是取mapsize = 2ˇ16 或者 80亿开方，一个map<int,int>大mapsize的空间不到1m

3. 顺序读80亿数据，除以mapsize取余，同一余数放追加同一文件,余数作文件名

4. 顺序读取步骤3产生的所有文件，读取的每个文件时新建mapsize大小的hashmap，统计每个数的次数，再取该hashmap中出现最多次数的整数放到新的map中

5. 依次读完步骤3 产生的文件，就能得到每个文件最多次数的整数map

所有步骤需要80亿数据的两次读盘，一次写盘，mapsize次取最大值，80亿数据取余数