25、算法与数据结构 - 实战：资源限制类题目
资源限制技巧汇总
1、 布隆过滤器用于集合的建立与查询，并可以节省大量空间；
2、 一致性哈希解决数据服务器负载管理问题；
3、 利用并查集结构做岛问题的并行计算；
4、 哈希函数可以把数据按照种类均匀分流；
5、 位图解决某一范围上数字的出现情况，并可以节省大量空间；
6、 利用分段统计思想，并进一步节省大量空间；
7、 利用堆、外排序来做多个处理单元的结果合并；
题目一
32位无符号整数的范围是0~4294967295，现在有一个正好包含40亿个无符号整数的文件，可以使用最多1GB的内存，怎么找到出现次数最多的数？
排序？不行，内存只有1G，无法在内存排序
1、 假设1G内存，使用hash表最多只能装下1千万条记录，那么40亿除以1千万，等于400，准备400个文件；
2、 然后每一个数，通过hash函数，算出一个hash值，模400，得到一个文件编号，该数发送到对应文件；
3、 此时同一个数字，只会进入一个文件，文件里面存的是该数字出现的次数；
4、 这样就搞成了400个文件，此时每次加载一个文件，遍历文件的每条记录，抓出出现次数最多的；
5、 最后这400个出现次数最多的数PK一下，得出整体出现次数最多的数；
6、 如果发现一个文件大小过大，在内存还是装不下，那么文件就搞500个、600个…；
如果题目要求返回出现次数最多的所有数，那么就拿着这个次数，到每个文件中再找一遍，看有没有出现这么多次的数，有的话就全部抓出来，返回。
题目二
32位无符号整数的范围是0~4294967295，
现在有一个正好包含40亿个无符号整数的文件，
所以在整个范围中必然存在没出现过的数。
可以使用最多1GB的内存，怎么找到所有没有出现过的数？
set去重统计？不行，内存会爆掉。
使用位图，8个bit才一个字节，那么就准备4294967295bit长度的位图进行统计。
如果实现bit数组？使用基础类型拼，长度为10的int数组，等于320bit长度的bit数组，第i个bit就是arr[i / 32]这个数的第i%32位
那么这一位代表的数是否存在，就这样计算：
intstatus = arr[i / 32] & (1 << (i%32)) != 0 ? 1 : 0;
如果status是1，那么就是存在，0就是不存在。
【进阶】
内存限制3KB，但是只用找到一个没出现过的数即可。
3KB大约能存下750个整形，那么准备一个离750最近的2的某次方，得到512，那么申请512长度的数组
此时可以把0~4294967295均分为512份（512个文件），每一份负责负责的范围的长度是8388608
这样，肯定在每个范围上存储数不满8388608的情况，找到这个不满的范围，再分512份，再找不满的小范围，再分512份…，几次过后就能找到没出现过的1个数。
【进阶】
内存中只能申请有限几个变量，但是只用找到一个没出现过的数即可。
申请两个变量L和R，对0~4294967295进行二分（两个文件）
统计两边出现的数的个数
其中有一边肯定不满，再对不满的一边进行二分，还是用两个变量L、R统计两边范围出现的数的个数
如此不断二分，最终会找到没出现过的1个数
题目三
有一个包含100亿个URL的大文件，假设每个URL占用64B，
请找出其中所有重复的URL
如果允许失误率，使用布隆过滤器
如果不允许，使用hash分流，分到不同小文件，看小文件是否有重复的。
【补充】
某搜索公司一天的用户搜索词汇是海量的（百亿数据量），
请设计一种求出每天人们Top100词汇的可行办法。
题目四
32位无符号整数的范围是0~4294967295，
现在有40亿个无符号整数，
可以使用最多1GB内存，
找出所有出现了两次的数。
用两个bit位表示一个数出现的次数，比如拿0bit位和1bit位表示0这个数出现的次数，00表示出现0次，01表示出现1次，10，表示出现两次，11表示出现3次或以上。
这样1个byte表示4个数。
但是4294967295除以4，超过了1G，那就继续用上面分段统计的办法。
也就是：位图 + 分段统计，先统计前面一半（0~2^31）出现两次的数，在统计后面一半的
题目五
32位无符号整数的范围是0~4294967295，
现在有40亿个无符号整数
可以使用最多3KB的内存，怎么找到这40亿个整数的中位数？
bfprt？不行，内存会爆掉。
3KB大约能存下750个整形，那么准备一个离750最近的2的某次方，得到512，那么申请512长度的数组arr。
此时可以把0~4294967295均分为512份（512个文件），每一份负责负责的范围的长度是8388608。
数组arr中每一个数统计自己范围内出现的数的个数。
中位数是第20亿个数，那么看数组arr累加到大于等于20亿，是数组arr中的第几个数。
假设arr[129]冲到了20亿，那么中位数一定在第129号文件。
然后以相同的方法，对129号文件分512份，数组arr统计每一份中出现的数的个数…循环往复，最终找到中位数。
题目六
32位无符号整数的范围是0~4294967295，
有一个10G大小的文件，每一行都装着这种类型的数字，
整个文件是无序的，给你5G的空间，
请你输出一个10G大小的文件，就是原文件所有数字排序的结果。
现在不看5G内存，假设内存严重不足，只能存几条记录
那么准备一个堆，大根堆，只存3条记录，存的是数字和出现的次数
申请1个10G的文件，用于存放结果
遍历文件，在堆中记录数字以及该数出现的次数：
假设遍历到3，记录 3 => 1，表示3出现1次
再遍历到3，记录 3 => 2，表示3出现2次
遍历到9，记录 9 => 1
遍历到7，记录 7 => 1
遍历到8，堆满了，弹出 9 => 1，记录8 => 1
遍历到6，堆满了，弹出 8 => 1，记录6 => 1
… 文件遍历完了，堆中就记录了整个文件中前3小的数，出现的次数
假设是 1=> 1000
3=> 2000
5=> 1000
然后在10G的文件中，数字1写1000次，数字3写2000次，数字5写1000次
然后用1个变量记录5，表示上一次遍历到的最大的数
再搞一遍这个遍历，在堆中记录数字以及该数出现的次数，但是小于等于5的数字不再记录
… 这样一直搞，直至所有的数都统计完（某一次循环，堆没放满），10G排序号的文件返回。
题目七
一个大文件，返回里面出现的数的前100名。
解法：分成不同的小文件，通过hash分流把数字分发到不同文件，每个文件统计Top100，然后在内存做归并排序。