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

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

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

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

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

1、将文件初始化。

按位比较，比如先遍历一遍数字，判断第一位是0还是1多，然后便利多的那一位的数字，判断第二位是0还是1多，依次判断到第32位，就是出现次数最多的数字了

好吧，这个算法不对

我感觉这个题目是不是考的排序算法啊，这80亿个数字如果是有序的，则根本不需要2G内存

如果是无序的，则2G内存不够用，那么肯定要引入额外硬盘空间，既然都引入额外硬盘空间了，那也不用这么多内存了。

所以我估计题目应该是这样：

需求：

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

假设：

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

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

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

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

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

64mb内存就够。假设你的数据都存在文件中。

1，分治法，空间换时间，分片读取hash到n个文件中

2，统计每个文件中出现次数最多的数字

3，堆排序，对比每个文件中出现次数最多的数字。

4，结束

只有不是程序员才会出这样的题，你要知道，3、8、55246546是整数，但12345的阶乘，葛立恒数等也是整数，葛立恒数的葛立恒数次方也是整数，你没有限定整数范围，所以我觉得真正的程序员会先和你谈需求。另，我就是程序员。

2G只能放5亿个整数。

先建个数组：

int num[5亿];

分页处理数字，每页5亿个。

第一次遍历数字

这是一个wordcount取max的计算 根据mapreduce思路 先将待统计的数据集分区 让相同的数字分到同一个分区 分区内进行groupby count后取max的一条 再与其它分区的max结果两两比较 保留较大的一条 最终结果就是全部数据里出现次数最大的一条

定义一个结构是a，数字，次数

建立动态数组，数组元素类型为结构a

初始数据有两个0和最大数。升序。

读取一块数据

扫描数据块，对每一个数字在数组中执行比较

假设1-80亿，每个数字都只出现一次，只有一个数字出现2次，你们的算法还行?。。。算法要考虑坏情况的