Table of Contents
在 leetcode 上看到了一道腾讯的面试题——2.5 亿数值数据查重。下面的回答很精彩，回答比较多的是异或法和位图法，因而查询了这两个算法的原理。因为还没有在 leetcode 上刷到这类题目，我 github 上的 leetcode repo 没有记录，故而在此记录一下。
异或法
按位异或属于位运算，记做 xor。规则是相同为 0，不同为 1。真值表如下：
| 1 | 0 | |
| 1 | 0 | 1 |
| 0 | 1 | 0 |
比如有 3 和 5 两个数，对其进行异或运算。
/** wordpress 数学表达输入不方便，用代码块表示吧
3 的二进制表示是 11
5 的二进制表示是 1001
11
xor 1001
---------
1010
1010 的十进制表达是 6
**/
再来看一个例子：0 xor 3
/**
0 的二进制表示是 0
3 的二进制表达是 11
0
xor 11
--------
11
**/
结合异或真值表和例子，我们可以发现，0 xor n = n。异或法解决数组查重正是基于这样一个基本原理。
比如：1 ^ 2 ^ 1 ^ 2 = 0, 1 ^ 2 ^ 1 = 2。
先不急着看位图法，我们先用异或法解决一些问题。
异或法解决数组查重问题
问题：
有 1 ~ 1000 的数值存在于长度为 1001 的数组中，其中只有一个数出现了两次，其余的均只出现一次。请找出那个重复的数。
解答：
根据题目，我们可以知道数组包含了 1 ~ 1000 的所有整数，并且有一个出现了两次。即，除了不知道哪个数重复外，其余的数都已经知道了。根据异或规则，我们只需要消去已知的数，剩下的就是重复的数。
(1 ^ 2 ^ 3 …… ^ 1000) ^ (1 ^ 2 ^ 3 …… ^ 1000) ^ n = T ^ T ^ n = n
所以：
// 模拟数据
let arr = new Uint32Array(1001)
for (let i = 0; i < 1000; i++) {
arr[i] = i + 1
}
arr[1000] = 887
// 模拟结束
// 解答
let res = arr[0]
for (let i = 1; i < 1001; i++) {
res ^= i
res ^= arr[i]
}
console.log(res) // 887
问题：
一个数组中只有一个数字出现了一次，其余的都出现了两次，找出这个孤单的数字。
解答：
这个问题直接一个遍历异或就可以了。
异或法虽好，可也有限制，比如要知道数值连续有限。比如 1，1，3 这种就不好用异或法。腾讯的这道面试题也是，并没有说数值连续。这种情况位图法会更好。
位图法
位图来自于 bitmap 说法，因为使用一个位来表示状态。对于数组查重这种问题，可以根据数组中的最大值 max，创建一个长度为 max + 1 的数组，然后遍历待查重数组，根据当前数值 n 设置新数组下标为 n 的元素为 1，当再次遇到已经置为 1 的元素的时候，就表示找到了重复的值。
位图法解决数组查重问题
鉴于 2.5 亿有点多，还是用 1 ~ 1000 示例。
问题：
有 1 ~ 1000 的数值存在于长度为 1001 的数组中，其中只有一个数出现了两次，其余的均只出现一次。请找出那个重复的数。
解答：
// 模拟数据
let arr = new Uint32Array(1001)
for (let i = 0; i < 1000; i++) {
arr[i] = i + 1
}
arr[1000] = 887
// 模拟结束
let res = null
let max = null
for (let i = 0, len = arr.length; i < len; i++) {
max = arr[i] > max ? arr[i] : max
}
let arr2 = new Uint8ClampedArray(max + 1)
for (let i = 0, len = arr.length; i < len; i++) {
if (arr2[arr[i]]) {
res = arr[i]
break
} else {
arr2[arr[i]] = 1
}
}
console.log(res) // 887
因为 JavaScript 的 Uint8ClampedArray 每个元素也需要占用 8 位，所以很难将内存占用降低到理想状态。如果每个元素都当作 8 个 1 位使用，不仅编码麻烦，数值转换也耗时。
其他
对于 1 ~ 1000 分布于 1001 长度数组这样数值连续有限的问题，还可以使用加减法完成。即所有元素相加，再减去 1 ~ 1000 范围的数值，多出来的就是重复的。但这种方法在顺序不固定时容易溢出。
位图法的思维很多时候可以用哈希表处理。JavaScript 的对象就是用哈希表实现的，所以可以直接使用。比如之前我为了对文本去重就用了对象。