22-《进阶》资源限制类问题.md

[TOC]

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

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

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

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

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

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

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

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

### 题目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次方个。接着二分不满的那个




### 题目2（位图）

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


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