# 第34节 资源限制类题目的解题套路
资源限制技巧汇总
1）布隆过滤器用于集合的建立与查询，并可以节省大量空间（已讲） 2）一致性哈希解决数据服务器的负载管理问题（已讲） 3）利用并查集结构做岛问题的并行计算（已讲） 4）哈希函数可以把数据按照种类均匀分流 5）位图解决某一范围上数字的出现情况，并可以节省大量空间 6）利用分段统计思想、并进一步节省大量空间 7）利用堆、外排序来做多个处理单元的结果合并
题目一
32位无符号整数的范围是0~4,294,967,295， 现在有一个正好包含40亿个无符号整数的文件， 可以使用最多1GB的内存，怎么找到出现次数最多的数？
使用技巧：
4）哈希函数可以把数据按照种类均匀分流
思路：
首先想到排序，拿个数组，一个int类型占用4B，40亿个int类型，占用160亿B=16G，超出了要求。
再次看到出现次数最多的数，这是词频，一般用HashMap搞定，但是40亿个数，最极端的情况就是40亿种数，那么一个键值对占用8Byte，放入40亿个，需要32G内存，超出了要求。
逆向想问题：
1）1GB能放入多少条HashMap数据，一个键值对占用8Byte，那么1G=1000,000,000B=10亿B，然后10亿/8=125,000,000=1亿2千5百万，为了防止内存爆掉，选取1亿条然后再除10，就是1千万条，40亿除以1千万就是400，准备0~399号文件。
2）利用哈希函数f1，将文件中40亿个数，假如a1经历f1算出哈希值再%400，假如取模的数是28，放入28号文件，40个亿数来一遍上述的操作，由于哈希函数的均匀性，那么这400个文件会均分40亿种数，1个文件差不多会是1千万种数，然后遍历400个文件，将0号文件中的数取出放入HashMap，统计这1千万种数中，出现词频最高的数，使用两个变量num是数值，times是出现次数，最终出现次数times最大的num，赋值给变量max，然后将1号文件中的数也进行相同的操作，出现词频最高的数再与max相比，谁大将值赋给max，周而复始，最后max就是出现次数最多的数
题目二
32位无符号整数的范围是0~4,294,967,295， 现在有一个正好包含40亿个无符号整数的文件， 所以在整个范围中必然存在没出现过的数。 可以使用最多1GB的内存，怎么找到所有未出现过的数？
使用技巧：
5）位图解决某一范围上数字的出现情况，并可以节省大量空间
思路：
首先想到是用HashSet统计数值是否出现过，一个int类型占用4B，40亿个int类型，占用160亿B=16G，超出了要求。使用位图表示数字是否出现，二进制位0是未出现，二进制位1是出现，需要准备bit[2^32]数组，占用的空间为(2^32/8)B=536,870,912B=537M，没有超出1G内存的要求。
1）将文件中40亿个数遍历一遍，假如一个数值为380，那么bit[380]=1，周而复始，完成赋值；
2）将bit[2^32]数组遍历，获取元素为0的索引位置，就是所有未出现过的数
如何实现bit[]数组？拿基础类型数组实现，例如上述需要bit[2^32]，那么就申请int[2^32/32=134,217,728] arr数组，因为一个int类型占用32位，arr[0]，定位方法是，bit[i] -> arr[i/32] 然后取出int类型，取出二进制位(i%32 )
获取状态：int status = (arr[i/32] & (1 << (i%32))) == 0 ? 0 : 1;【进阶】 内存限制为 3KB，但是只用找到一个没出现过的数即可
使用技巧：
6）利用分段统计思想、并进一步节省大量空间
进阶思路：
如果3KB的空间都拿它来做int[]，那么数组长度最大是多少？3000/4=750，离750最近但是比它小的2的9次方数是512，申请int[512]，那么就将32位无符号整数的范围是2^32分为512份，一份是管理2^32/512=8,388,608个数值范围，比如int[0]管理0~8,388,607的数值范围上出现的词频，若是int[i]中统计的出现词频数小于8,388,608，然后再int[i]管理的范围上512分，一定在小范围中有不满的小范围，再这个小范围上再512分，递归起来，用不了几次，最终会找出没有出现的一个数
扩展：假设只能申请有限几个变量，只用找到一个没出现过的数即可
扩展思路：二分法
申请L、mid、R三个变量，L=0，R=2^31-1，mid=2^31，统计左侧范围出现的词频，再统计右侧范围出现的词频，一定有不够2^31的那一侧，再二分，一定有一侧不够，再次二分，最终会找出没有出现的一个数
题目三
有一个包含100亿个URL的大文件，假设每个URL占用64B，
要求限制很少的内存，请找出其中所有重复的URL
使用技巧：
4）哈希函数可以把数据按照种类均匀分流
思路：
如果允许有失误率那么使用布隆过滤器实现，如果不能有失误率那么就使用哈希再哈希的方法分流；
1）将大文件中的url通过哈希函数f1，再%m，url均匀分布在m个文件中，若是一个m文件中url还是很多；
2）再将m文件中的url通过哈希函数f2，再%k，url均匀分布在k个文件中，然后再k的文件中查找重复的URL，统计词频超过1的数值，输出就行了
【补充】 某搜索公司一天的用户搜索词汇是海量的(百亿数据量)， 请设计一种求出每天热门Top100词汇的可行办法
使用技巧：
4）哈希函数可以把数据按照种类均匀分流
7）利用堆、外排序来做多个处理单元的结果合并
思路：堆上堆 二维堆
运用上面的能够把找出所有重复的URL，这次取出m*k个文件中每个文件求出它的Top100，将每个文件Top1，放入大根堆中，堆里数据是键值对("词汇","来自的文件号")，从堆中弹出数据，作为Top1，假定Top1来自6号文件，则将6号文件查找排除Top1的词汇后最多的词汇，放入堆中，再堆中弹出数据，作为Top2，周而复始，直到Top100
题目四
32位无符号整数的范围是0~4294967295， 现在有40亿个无符号整数， 可以使用最多1GB的内存， 找出所有出现了两次的数。
使用技巧：
5）位图解决某一范围上数字的出现情况，并可以节省大量空间
6）利用分段统计思想、并进一步节省大量空间
思路：
利用位图，这次是两个二进制位表示00->没有出现，01->出现一次，10->出现两次，由于两个二进制位代表一个数字的状态位，所以需要准备bit[2^32*2=2^33]数组，占用的空间为(2^33/8)B=1,073,741,824B=1073M，超出1G内存的要求，可以利用分段统计的思想，先统计左侧(0~2^31)范围上的出现了两次的数a，再解决右侧(2^31~2^32-1)范围上的出现了两次的数b，最后a+b
题目五
32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数 可以使用最多3K的内存，怎么找到这40亿个整数的中位数？
使用技巧：
6）利用分段统计思想、并进一步节省大量空间
思路：
找到这40亿个整数的中位数，就是找到20亿的这个数。
如果3KB的空间都拿它来做int[]，那么数组长度最大是多少？3000/4=750，离750最近但是比它小的2的9次方数是512，申请int[512]，那么就将32位无符号整数的范围是2^32分为512份，一份是管理2^32/512=8,388,608个数值范围，我在这512份数据中找到第一次超过20亿的范围，比如int[0]管理0~8,388,607的数值范围上出现的词频3亿，那么就知道我要找的20亿的中位数绝对不在这个范围上，再假设int[0]+int[1]+int[2]=18亿，那么这三个范围都不是我要找的范围，最后int[3]=3亿，第一次超过了20亿，说明int[3]范围上肯定有我要找的中位数，再int[3]管理个数划分512份，再这512份数据中找到第一次超过2亿的范围，递归下去，最终找到中位数。
题目六
32位无符号整数的范围是0~4294967295， 有一个10G大小的文件，每一行都装着这种类型的数字， 整个文件是无序的，给你5G的内存空间， 请你输出一个10G大小的文件，就是原文件所有数字排序的结果
使用技巧：
7）利用堆、外排序来做多个处理单元的结果合并
思路：门槛堆的设计技巧
1）假设大根堆，容量只有3，放入键值对数据("数值"，"词频")遍历文件，当堆中容量少于3时，一直放入数值，并且当堆中数值存在时，词频加1，当堆中容量等于3时，要放入的数值小于堆顶数值，则弹出数据，放入数值，并记录词频，遍历下来，堆中记录着，最小的三个数值及所属词频，将堆中数据弹出，并写入文件中，遍历词频个数，然后打印数值，然后清空了堆
2）重复1步骤，但是排除那三个值，周而复始
3）最终得到原文件所有数字排序的结果