[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的状态
- 第一节 复杂度、排序、二分、异或
- 第二节 链表、栈、队列、递归、哈希表、顺序表
- 第三节 归并排序、随机快排介绍
- 第四节 比较器与堆
- 第五节 前缀树、桶排序以及排序总结
- 第六节 链表相关面试题总结
- 第七节 二叉树基本算法
- 第八节 二叉树的递归思维建立
- 第九节 贪心算法深度剖析
- 第十节 并查集、图相关算法介绍
- 第十一节 暴力递归思维、动态规划思维建立
- 第十二节 用简单暴力递归思维推导动态规划思维
- 第十三节 单调栈和窗口及其更新结构
- 第十四节 类似斐波那契数列的递归
- 第十五节 认识KMP算法与bfprt算法
- 第十六节 认识Manacher(马拉车)算法
- 第十七节 认识Morris遍历
- 第十八节 线段树
- 第十九节 打表技巧和矩阵处理技巧
- 第二十节 组累加和问题整理
- 第二十一节 哈希函数有关的结构和岛问题
- 第二十二节 解决资源限制类题目
- 第二十三节 有序表原理及扩展
- 第二十四节 AC自动机和卡特兰数
- 第二十五节 算法面试专题-链表
- 第二十六节 算法面试专题-二叉树
- 第二十七节 算法面试专题-字符串