1 如何解决资源限制类题目

1.1布隆过滤器用于集合的建立与查询，并可以节省大量空间（已讲）

1.2 一致性哈希解决数据服务器的负载管理问题（已讲）

1.3 利用并查集结构做岛问题的并行计算（已讲）

1.4 哈希函数可以把数据按照种类均匀分流

1.5 位图解决某一范围上数字的出现情况，并可以节省大量空间

1.6 利用分段统计思想、并进一步节省大量空间

1.7 利用堆、外排序来做多个处理单元的结果合并

1.7.1 题目1（位图和分段统计）：

32位无符号整数的范围是0~4,294,967,295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数。

1、可以使用最多1GB的内存，怎么找到所有未出现过的数？

【进阶】

2、内存限制为 10MB，但是只用找到一个没出现过的数即可

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

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

如果用HashMap来存所有的key，每个无符号整数是4个字节，40亿个数，大约160亿字节，10亿字节大约1G, 大约需要16个G内存才能存下

第一问题解利用位图

如果限制1GB，那么可以使用位图，0到2的32次方减1范围的无符号数，只需要2的32次方个bit来存记录。Hash表需要4个字节才能表示一个数出现过还是没出现过，Bit来代表一个数出现过还是没出现过，空间上缩小了32倍。原本使用Hash需要的16G空间，现在缩小32倍，大约500M可以拿下==对应第五点==

第二问和第三问题解利用分段统计

当限制10M,或者3K,那么位图也失效了。位图解决该问题大约500M。

拿3K举例，3KB（字节）如果都做成整形数组的的话，3KB除以4等于750个容量；

接着我们找到离750最近的2的某次方，找到512。那么我们把我们的数组申请512长度，一定不会超过3KB；

根据给定的范围，我们的数据大概有2的32次方个数字；且2的32次方，一定能够被512均分；均分为8388608份；512个位置的0位置统计0到8388608范围上出现了几次，1位置统计8388609到8388608*2范围上的数出现了几次，依次类推；每统计一个数，让该数除以8388608得到属于512个位置的哪个位置，该位置统计的数加1；

经过统计，512个位置，至少有一个位置统计的个数，不够8388608个，找到该位置代表的数据范围。该范围大小再除以512，得到新的512个数统计的新范围，循环往复，那么一定能够找到一个数没出现过

第四问题解

三个变量找没出现过的一个数，运用二分来找。第一次二分，如果2的32次方的数都有，那么左右两边都是2的31次方。由于只有40亿个数，那么左右两侧必定有不满2的31次方个。接着二分不满的那个

1.7.2 题目2（位图）

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

参考题目1，也采用位图的思想，使用位图中的两位来表示一个数有没有出现过，且出现了几次。当两位的状态变为11，那么维持住。最后统计10的状态

本站文章除注明转载/出处外，均为作者原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2022/11/02 00:42

22如何解决资源限制类题目