算法与数据结构进阶课第十一节笔记

进阶课第十一节笔记"/>

算法与数据结构进阶课第十一节笔记

资源限制类题目

1）布隆过滤器用于集合的建立与查询，并可以节省大量空间（已讲）
2）一致性哈希解决数据服务器的负载管理问题（已讲）
3）利用并查集结构做岛问题的并行计算（已讲）
4）哈希函数可以把数据按照种类均匀分流
5）位图解决某一范围上数字的出现情况，并可以节省大量空间
6）利用分段统计思想、并进一步节省大量空间
7）利用堆、外排序来做多个处理单元的结果合并

题目1：

32位无符号整数的范围是0~4,294,967,295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有未出现过的数？
【进阶】
内存限制为 10MB，但是只用找到一个没出现过的数即可

内存限制为 3KB，但是只用找到一个没出现过的数即可

内存限制为 四个变量，但是只用找到一个没出现过的数即可

普通问题：32为无符号整数使用位图的话，就可以表示任何一个无符号整数，就能统计

进阶问题1,2：

3KB 可以表示了整型数组长度是3KB/4 约为750，找离750最近的2的某次方，就是512，那么把数组定为512的长度，一定不会越界

无符号整数有2的32次方，那么一定能被512均分，每一份里面有8388608个数，通过num/8388608就能知道分到哪一组，就让第0份统计0-8388608范围 上出现了几个数

第1份统计8388609-8388608*2范围上出现了几个数，依此类推每一份都统计好。必在某个范围内他的词频统计不够8388608，那么就将这个范围再在3KB上重新分成512份，一直做词频统计和分组，直到能够用bit数组表示出现没有。

进阶问题3：

做二分，在左右两边使用两个变量统计词频，再从不足一半数量的开始二分统计，一直到剩一个数，就是其中一个没出现的数，二分32次，一个L，一个R，一个M，一个词频统计。

题目2：

32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数，可以使用最多1GB的内存，找出所有出现了两次的数。

使用两个bit去表示出现的次数，00 表示 没有出现，01 表示出现 1 次，10 表示出现 2 次，11 表示出现了更多次，从3次开始以后再出现就不再变化，所有10的数就是出现两次的数

题目3：

有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL
【补充】
某搜索公司一天的用户搜索词汇是海量的(百亿数据量)，
请设计一种求出每天热门Top100词汇的可行办法

利用一个hash函数取得这个url的hash code，对n取摩，将整个URL均分在n个文件中，那么相同的URL一定会被分在相同的文件中，如果还是大，就继续把每个文件按另一个哈希函数分成m个，有多个机器就先分到每台机器去，一台机器不够就继续拆成小文件，最后统计汇总

补充问题：

大体流程：先按上面的流程分成小文件，计算出小文件里的top100，再汇总计算整体的top100

外排方式，每个文件的top都从大排好序，然后从每个文件顶部做比较，得出最大的，记录后删除，这样它下面的记录就变成了文件顶部，继续进行比较，记录最大删除的操作

堆方式：每个小文件内部做成大根堆heap1..n，每个小文件的顶部元素也组成一个大根堆heapTop，出了一个最大词频，它所在的文件内部调整为大根堆结构，然后让现在这个大根堆的堆顶加入文件顶部元素组成的那个大根堆heapTop，再进行调整，完事之后，heapTop的堆顶就是第二个热搜词

题目4：

32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数，可以使用最多10MB的内存，怎么找到这40亿个整数的中位数？

书中312页，不哈希，就是分组来统计词频0~X的范围里的数进arr[0] 统计等

题目5：

32位无符号整数的范围是0~4294967295，有一个10G大小的文件，每一行都装着这种类型的数字，整个文件是无序的，给你5G的内存空间，请你输出一个10G大小的文件，就是原文件所有数字排序的结果。

准备一个保存较大值的小根堆，再准备一个保存小根堆里词频的map，key是num，value是出现次数，遍历这10G的大小文件的数字，依次建成一个内存能允许的大小的小根堆，后面的数字和堆顶做比较，小于堆顶直接跳过，大于堆顶，替换堆顶后调整堆结构，在map里把原堆顶的记录剔除，增加新加入的数字的词频，全部遍历完，依次出堆就能得到一个整体较大值且有序的记录，再次遍历，让所有比刚刚已经生成记录的数字小的数字再次组建小根堆，剔除，记录词频，一直到所有的数字都排好序

最后根据序列和词频还原成10G的文件

可以按行读取文件，所以占用内存并不大