前端也有算法 - 位图法

一不小心就看到位图法，引起了我的兴趣。
简单说下位图法（bitmap），用每一个bit来存放某个状态，常用于正整数类型中。（具体内容请自行百度）

先来个抛砖引玉吧，曾经有一个题目，据说是腾讯的前端面试题，内容大概如下：

示例一（已删数字）：

题目：

有一组数字，从1到n，假设n=10，乱序且不重复。例如[1,5,8,3,4,9,2,6,7,10]，随机删除3个数字，请找出3个被删除的数字。

算法：

1. 以最大数字n=10来初始化位图数组
2. 循环剩余数字，把状态位设置进位图数组里面（复杂度N）
3. 循环状态位数组，把状态位不为1的提取到输出结果数组（复杂度N）
4. 总复杂度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]，请合并去除重复数字，并找出重复过的数字。

算法：

1. 找出两个数组中最大的数字，用于构建位图数组， max=10（此步骤不做处理）
2. 把已知的第一个数组写进位图数组里（复杂度N）
3. 把已知的第二个数组与位图数组做比对，状态位为1的则是已存在的数字，即重复数字，比对完后也写进位图数组里（复杂度N）
4. 循环位图数组，提取所有数字，即可得出合并后的数组（复杂度N）
5. 总复杂度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的计算了

位图法总结

1. 只能用于正整数
2. 支持排序
3. 支持去重
4. 支持亿量级别计算
   至于使用场景，需要自己摸索，至少比二叉树的实际使用场景多