数组查重算法——异或法和位图法

在 leetcode 上看到了一道腾讯的面试题——2.5 亿数值数据查重。下面的回答很精彩,回答比较多的是异或法和位图法,因而查询了这两个算法的原理。因为还没有在 leetcode 上刷到这类题目,我 github 上的 leetcode repo 没有记录,故而在此记录一下。

异或法

按位异或属于位运算,记做 xor。规则是相同为 0,不同为 1。真值表如下:

10
101
010
异或真值表

比如有 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 的对象就是用哈希表实现的,所以可以直接使用。比如之前我为了对文本去重就用了对象。