# 资源限制类题目解题思路
# 资源限制类技巧汇总
1）布隆过滤器用于集合的建立与查询，并可以节省大量空间
34节布隆过滤器,利用位图,哈希函数,大量节省空间的算法,但是有误差且无法避免.
2）一致性哈希解决数据服务器的负载管理问题
34节一致性哈希,环形结构+虚拟节点,保证均匀分布.
3）利用并查集结构做岛问题的并行计算
16节并查集,分块并行计算,记录边界是由哪个点合并而来的,最终合并时,得到的是合集后的结果.
4）哈希函数可以把数据按照种类均匀分流
一句话就是 哈希来,哈希去,一个大文件,内存有限,直接用哈希表会爆,那就是先哈希到一个个小机器上,再哈希到不同的小文件上,然后直到内存够用了,再业务计算.例题:题目一,题目五
他不怕一个数个数太多,怕的是种数太多,一个数多了,就是v++.
5）位图解决某一范围上数字的出现情况，并可以节省大量空间
位图!!!一个字节,1Byte,也就是8个字节,8个位置,可以替代8个位置是否出现过,例如,00101110代表1,2,3,5出现过,0,4,7,8没出现.
例如:问题2
出现没出现,像不像布隆过滤器啊
6）利用分段统计思想、并进一步节省大量空间
一次性我吃不下,我分段一点点吃.例题:题目三,题目四
7）利用堆、外排序来做多个处理单元的结果合并
# 题目一,有限资源找到出现次数最多的数
32位无符号整数的范围是0~4,294,967,295， 现在有一个正好包含40亿个无符号整数的文件， 可以使用最多1GB的内存，怎么找到出现次数最多的数？
首先分析,如果无限制,40亿,整数1个是4字节,那就是160亿Byte,排序内存需要16G,但是我只有1G
如果我们是哈希表,key,v,假设啊,1,出现40亿次,实际存储的,就是2个int值,k是1,v是40亿.但是我们要按最差情况估计,40亿*8,还不如刚才的40亿*4.
我们这么干,首先,我们算一下1GB能装下多少哈希值,假设就是一对kv,8个字节,差不多1.25亿.我们可能还有些别的要耗内存,我们缩小10倍总可以吧,一次假设就1kw条.我们40亿/1kw=400.我们要讲这40亿数据分堆.
我们给每个数,通过哈希函数%400,这些数据一定会均匀分布到400个小文件中,且相同的值一定在同一个文件中.每个文件都是1kw左右.
我们再用哈希表,来一个个的看看每个文件出现最多的数是多少,kv8字节*1kw.内存一定不会爆.用完了我记住第一个,剩下的就放了.
这样我们400个小文件一个个过一遍,每个第一名再求一次最多的,就得到了结果.
# 题目二,有限资源,找到所有未出现的数
32位无符号整数的范围是0~4,294,967,295， 现在有一个正好包含40亿个无符号整数的文件， 所以在整个范围中必然存在没出现过的数。 可以使用最多1GB的内存，怎么找到所有未出现过的数？ 【进阶】 内存限制为 3KB，但是只用找到一个没出现过的数即可
同样的,全部放到内存里,40亿需要16G内存,而我们用位图来做,2^32个bit,也就是2^32/8个Byte,1G内能拿下!!
用byte拼,例如arr[10]可以装40Byte,320bit,我们让arr[0]负责0~31,arr[1]负责32~63....
假设,我现在取,34位,先/32,看看到那个位置上去拿,就是第一个,然后,我再%32,看看到第几位去拿,应该是2,整体的34位.怎么拿?
假设:数据是这样的34位(第一个数第2位)是1
...001110100
...000000100 1左移2位就是这样,与一下,结果如果有剩下,则是1.
...000000100 与的结果
如果说是0 那与完了肯定啥也不剩.
...001110000
...000000100 1左移2位就是这样,与一下,结果如果有剩下,则是1.
...000000000 与的结果
int[] arr = new arr[10];
//arr[0] int 32位
//.....
//arr[9] int 32位
int i = 179;
int status = (arr[i/32] & (1<<(i%32))) == 0 ? 0 : 1
# 题目三,有限资源,找到一个没出现的数
32位无符号整数的范围是0~4,294,967,295， 现在有一个正好包含40亿个无符号整数的文件， 内存限制为 3KB，但是只用找到一个没出现过的数即可
【思路】
3KB的内存如果都用来做无符号的整型数组，数组最长能有 3000/4 = 750 的长度
然后找一个离 750 最近的2的某次方，即 2^9= 512，那如果无符号整型数组申请 512 长度是不会超过限制内存的，即int arr[512]，不会爆掉.
无符号整型整数的范围是0~2^32 -1，整个范围是 2^32，将这个范围均分为 512份，即2^32/512 = 8388608，每份包含的范围是一样大的。也就是第一份负责统计0~8388608这个范围的数字出现的次数注意是次数，第二份统计 8388609~8388609+8388608 这个范围出现的次数，以此类推。又因为数组长度为 512，所以 arr[0]统计第一份的范围上的数字共有多少个，arr[1]统计第二份的范围每个数字出现的次数，以此类推。 注意,我这个512长度的数组,每一块都是一个int,都最大能表示0~4,294,967,295,所以即使所有数组都在这个范围,也不会爆,我统计的是数量,一共才40亿个数,如果统计数量大于8388608也没有关系,平分512份,一定有不满8388608的,我只在不满的范围找.
而提给定的数的个数是40亿，而整数范围是0~约43亿，那么就会导致某个区间的词频统计不到 8388608(注意是词频统计，不是数字个数!!)，找到那个不满 8388608的小区间，在这个小区间中找到没有出现过的数即可。而在这个小区间中怎么找没有出现过的数呢?将小区间分成 512 份更小的区间，在这个更小区间中一定又有不满的，又将该不满的区间分成512份，只需几次就能定位到没有出现过的数
总结:3KB内存的情况时，进行 512分。
# 题目四,仅用几个变量,找到1个没出现过的数
32位无符号整数的范围是0~4,294,967,295， 现在有一个正好包含40亿个无符号整数的文件， 仅用有限几个变量,但是只用找到一个没出现过的数即可
一开始，准备三个变量，L在0位置，R在 2^32-1 位置，mid 在L~R中间的位置，如此一来，L~mid 和 mid~R 范围都应该是 2^31(一半)，但是因为只有 40 亿个数，那么必然存在左右两侧其中一侧范围词频统计不足一半(不足2^31个数)的情况，将不足的这一侧范围又进行二分，递归该过程，直到找到没有出现过的数。 总结:3kb的时候,就是512分,有限几个变量的时候，就是二分
# 题目五,100亿个url,找到所有重复的url
有一个包含100亿个URL的大文件，假设每个URL占用64B， 请找出其中所有重复的URL
这个就是不允许有失误率的,如果允许有失误率,考虑布隆过滤器.
如果不允许失误率,那就哈希来,哈希去,分流,先给这个大文件哈希到不同的小文件,然后再哈希到不同的小文件,最后检查每个小文件中重复的url.
# 题目六,找到出现2次的数
32位无符号整数的范围是0~4294967295， 现在有40亿个无符号整数， 可以使用最多1GB的内存， 找出所有出现了两次的数。
出现了2次,我用2位来替代,例如,00 01 10 11代表0123四个数出现次数,2位代表一个数,00代表没出现过,01代表1次,11代表3次及以上次,10代表2次,那我最后返回位置是10的数即可.
同样的,如果我想返回出现5次的,我可以用3位代表他,101就是5次.
# 题目七,有限资源,找到40亿个数的中位数
32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数 可以使用最多3K的内存，怎么找到这40亿个整数的中位数？
根据题目3,我们可以把40亿个数,分成512份,那我们求的是中位数,中位数就是第20亿个数.
所以这个值肯定不在第一个分组里,也不在最后一个分组里,大概在中间的分组里.在哪个呢.
平均一个8388608个数,肯定有不到的,我们一个个加起来,直到正好兜住20亿的时候,例如256个是19亿5k,加上第257个分组,20亿1k了,这个中位数肯定在第257分组里,我们再给这个分组的数分512份,然后直到找到第20亿个数.
# 题目八,有限资源,给超过资源的文件排序
32位无符号整数的范围是0~4294967295， 有一个10G大小的文件，每一行都装着这种类型的数字， 整个文件是无序的，给你5G的内存空间， 请你输出一个10G大小的文件，就是原文件所有数字排序的结果
堆!
我做一个门槛堆,做一个堆排序,记录数,和出现次数,过一遍所有的数,我记录着从小到达的堆最大空间范围个数,
走完一遍后,将堆里的数据写到文件里,然后拿一个t,记录下最大的值,再过一遍数据,小于这个值的看都不看,
循环过几次,很快就排序完了输出了.
← 与哈希函数有关的数据结构 数组三连问题. →