资源限制类问题的常用解决方案
说明
以下提到的数据结构和元素类型均基于Java语言。
问题1
32位无符号整数的范围是
0~4,294,967,295(即：0 ~ 2^32 - 1）现在有一个正好包含40亿个无符号整数的文件，可以使用最多1GB的内存，怎么找到出现次数最多的数？
首先，需要考虑最差情况，假设40亿个数都不一样。
如果使用Hash表，key表示其中的某个数，value表示出现的次数，由于
40亿 > Integer.MAX_VALUE
所以Hash表的key和value都需要long类型来存，
Hash表中的每条记录至少需要
8Byte + 8Byte = 16Byte
最差情况，40亿条不同记录进入Hash表，
需要
16Byte * 40亿 = 640亿Byte
约等于64G。内存不够。
如果申请数组来存，由于Java中数组长度有限制(Integer.MAX_VALUE)，所以要存下40亿个数，一个数组一定不够。
long类型的多个数组假设把所有40亿个不同的数都存下，
需要的内存空间是：
40亿 * 8Byte = 320亿Byte
约等于32G, 内存也不够。
如果只有1G内存，如果用Hash表，key和value均为long类型，即一条记录大约8Byte，保守估计，可以装下
1G / 8 Byte = 10亿Byte / 8Byte = 1.25亿，
在这个1.25亿基础上再减少到1千万， 处理1千万种类的数据，绝对不会超过现有的内存限制。通过如下计算
40亿 / 1千万 = 400
我们可以创建400个空文件，然后，对于每一个数m，通过hash函数得到一个hash值，假设m的哈希值为n, 然后用n
hash(m) % 400 = n % 400 = i
得到的i的值是多少，就把m这个值分配到第i号文件中。
根据hash函数的性质，相同的数一定进入同一个文件。 且400个文件中每个文件大约都是1千万种数。
使用hash表统计每个文件中出现次数最多的数（最多1千万种左右，hash表在现有资源限制下无压力），就是整个文件出现次数最多的数。
问题2
32位无符号整数的范围是
0~4,294,967,295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数, 可以使用最多1GB的内存，怎么找到所有未出现过的数？
如果使用HashSet，需要用long类型来存，大约需要
40亿 * 8Byte = 320亿Byte
大约32G，内存不够。
我们可以使用bit数组(位图)来存每个数是否出现，0表示出现，1表示没有出现。Java中，一个int类型可以表示32位， 因为要标识每个数是否出现过。所以2^32个数大约需要
(2^32) / 8 = 537M
537M空间的内存占用，满足限制条件。
Java中，因为每个int数字可以表示32位的二进制数，所以可以使用int数组来构造位图,
参考如下示例代码(179这个数字是否出现过)：
int[] arr = new int[10];int i = 179;int status = (arr[i / 32] & (i << (i % 32 ))) == 0 ? 0 : 1
status = 0则表示没有出现过，status = 1则表示没有出现过。
问题3
32位无符号整数的范围是
0~4,294,967,295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数, 内存限制为3KB，只用找到一个没出现过的数即可。
3KB 如果用来表示long类型的数组，数组最大长度大约是
3KB / 8Byte = 375。大约375长度, 然后我们寻找比375小的离375最近的2的某次方的数，得到256, 那我们可以申请一个256长度的long类型数组，假设叫arr。
由于数字一共有2^32次方个，我们可以将
2^32 / 256 = 16,777,216
均分成256份，每一份负责统计每16,777,216个数出现的次数。
arr[0] 统计 0 ~ 16,777,215出现的次数。
arr[1] 统计 16,777,216 ~ （16,777,216 + 16,777,215） 出现的次数。
.....
arr[255] 统计 （2^32 - 1 - 16,777,215） ~ 2^32 - 1 出现过的数。
由于现在的数个数是40亿, 不到2^32次方，所以，肯定有某个位置上的arr值不够16,777,216个。 由于只需要找到一个没有出现过的数，所以只需要在不够16,777,216这个范围的位置上进行再一次的256份的划分，然后再次使用上述逻辑，直到划分到某个数单独作为一个范围同时没出现过，这个数就是我们需要找的数。
问题4
32位无符号整数的范围是
0~4,294,967,295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数, 只能使用有限几个变量，如何找到一个没出现过的数（找到一个即可）。
参考问题3，我们可以设置一个变量L定位第0个数，设置变量R定位2^32-1上的数，设置M变量定位到中间位置。由于一共有2^32次方个数，所以统计左边和右边都应该有2^31个数，但是总共40亿个数，所以必然有一边不满足2^31方个数，然后不满足的这一边继续二分，重复上述逻辑，即可找到没有出现过的一个数字。
问题3和问题4类似，我们可以得到一个结论： 如果内存3KB，就用256分，如果是几个变量，就用二分。
问题5
有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL。
如果允许失误率，这个问题可以使用布隆过滤器来解决。
如果不允许失误，则可以使用问题1的方法，Hash函数结合取模操作，分到小文件思想。
问题6
32位无符号整数的范围是
0~4294967295，现在有40亿个无符号整数，可以使用最多1GB的内存，找出所有出现了两次的数。
问题2中，我们拿一个bit来表示一个数出现过一次或者没出现过，本问题我们可以拿两个bit来表达一个数出现的次数。
00表示没出现
01表示出现过1次
10表示出现过2次
11表示出现过3次及3次以上
问题7
32位无符号整数的范围是
0~4294967295，现在有40亿个无符号整数, 可以使用最多3KB的内存，怎么找到这40亿个整数的中位数？
参考问题3的做法，把整个2^32个数均分到一个256长度的long型数组中，每个位置管理16,777,216个数出现的次数。 然后逐个累加区间中数字出现的次数，一直累加到21亿左右，即可判断，中位数一定存在这个区间中。
问题8
32位无符号整数的范围是
0~4294967295，有一个10G大小的文件，每一行都装着这种类型的数字，整个文件是无序的，给你5G的内存空间，请你输出一个10G大小的文件，就是原文件所有数字排序的结果。
我们定义一个数据结构
class Node { long value; long times;
}value表示文件中的数值，times表示文件中的数值出现的次数。
然后设置一个大根堆存Node。value大的数值在堆顶， 假设堆大小我们设置为3，每次遍历的数和次数加入大根堆。大根堆满了以后，如果新加入一个大根堆中没有的数，则比较新加入的数和大根堆堆顶元素，如果比堆顶元素小，则剔除堆顶元素，加入新元素。遍历一轮以后，大根堆中的三个数一定是整个文件中最小的三个数。然后把这三个数和次数依次写入新文件，然后继续上述遍历和处理。每次都可以拿到三个排序后的数值，直接加入到新文件即可。
所以，因为本问题中有5G内存，根据我们上述的方案，绰绰有余。
问题9
某搜索公司一天的用户搜索词汇是海量的(百亿数据量)，请设计一种求出每天热门Top100词汇的可行办法。
参考问题1，我们可以使用Hash函数结合取模操作，分到小文件思想。
然后使用大根堆，统计每个文件中的top100。
最后，把每个文件对应的大根堆的堆顶元素弹出放入新的一个大根堆（假设这个大根堆叫superHeap）中。然后从这个新的大根堆的堆顶弹出堆顶元素，即为全局top1。
然后看这个弹出的堆顶元素是来自于哪个文件，继续把这个文件对应的大根堆堆顶元素弹出，继续放入superHeap中，然后从superHeap弹出堆顶元素，就是全局top2。
.....
依次类推，直到top100。
来源https://www.cnblogs.com/greyzeng/p/15371414.html