一不小心就看到位图法，引起了我的兴趣。
简单说下位图法（bitmap），用每一个bit来存放某个状态，常用于正整数类型中。（具体内容请自行百度）
先来个抛砖引玉吧，曾经有一个题目，据说是腾讯的前端面试题，内容大概如下：
示例一（已删数字）：
题目：
有一组数字，从1到n，假设n=10，乱序且不重复。例如[1,5,8,3,4,9,2,6,7,10]，随机删除3个数字，请找出3个被删除的数字。
算法：
- 以最大数字n=10来初始化位图数组
- 循环剩余数字，把状态位设置进位图数组里面（复杂度N）
- 循环状态位数组，把状态位不为1的提取到输出结果数组（复杂度N）
- 总复杂度2N，N∈正整数
// 随机删除后的数组
var arr = [1, 3, 4, 9, 2, 7, 10];
// 位图数组，多了索引0，所以设置11个
var bitmap = Array(11);
// 输出数组
var outputArr = [];
// 设置位图状态
for (var i = 0; i < arr.length; i++) {
bitmap[arr[i]] = 1;
}
// 提取已移除的数字
for (var i = 1; i < bitmap.length; i++) {
if (!bitmap[i]) {
outputArr.push(i);
}
}
// 输出[5, 6, 8]
console.log(outputArr);
原理：
初始化的位图数组如下：
[undefind * 11]
设置状态位后的位图数组（undefind当0）如下：
[0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1 ]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
不难看出，缺失的5,6,8，位图法就是通过这种原理来设置的
另外，位图法还支持排序，从上得知数字也被重新排好序了
示例二（去重）：
题目：
已知两个数组[8,4,6,2,1,9]、[3,4,5,8,9,7,0]，请合并去除重复数字，并找出重复过的数字。
算法：
- 找出两个数组中最大的数字，用于构建位图数组， max=10（此步骤不做处理）
- 把已知的第一个数组写进位图数组里（复杂度N）
- 把已知的第二个数组与位图数组做比对，状态位为1的则是已存在的数字，即重复数字，比对完后也写进位图数组里（复杂度N）
- 循环位图数组，提取所有数字，即可得出合并后的数组（复杂度N）
- 总复杂度3N，N∈正整数
var arr1 = [8, 4, 6, 2, 1, 9];
var arr2 = [3, 4, 5, 8, 9, 7, 0];
var bitmap = Array(10);
// 重复的数字
var repeatArr = [];
// 合并后的数组
var concatArr = [];
// 设置位图状态
for (var i = 0; i < arr1.length; i++) {
bitmap[arr1[i]] = 1;
}
// 找到重复数字
for (var i = 1; i < arr2.length; i++) {
if (bitmap[arr2[i]]) {
repeatArr.push(arr2[i]);
}
// 同时设置位图状态
bitmap[arr2[i]] = 1;
}
// 合并后的数组
for (var i = 0; i < bitmap.length; i++) {
if (bitmap[i]) {
concatArr.push(i);
}
}
// 输出[4, 8, 9]
console.log(repeatArr);
// 输出[0, 1, 2, 4, 5, 6, 7, 8, 9]
console.log(concatArr);
数量级别：
位图法能不能计算数以亿计的量级，答案是“能”
一个bit状态位表示一条数据，
我们来简单计算一下：
1B = 8bit
1KB = 1024B
1MB = 1024KB
≈ 1024 * 1024 * 8 bit
≈ 840万 bit
也就是说，800多万的数据才占用了1MB内存而已，剩下的就是cpu的计算了
位图法总结
- 只能用于正整数
- 支持排序
- 支持去重
- 支持亿量级别计算
至于使用场景，需要自己摸索，至少比二叉树的实际使用场景多
