Thinking--快速找出故障机器(异或)
Thinking系列，旨在利用10分钟的时间传达一种可落地的编程思想。
假设一个机器仅存储一个标号为ID（数值）的记录，且该数据会保存备份(即，两个机器存储了同样的数据；类似于双节点部署)。
- 在某个时间，如果得到一个数据文件ID的列表，是否能够快速找出这个列表中仅出现一次的ID？
- 如果已知道有一台机器死机呢？如果两台呢？
const originList = [123, 456, 789, 134, 123, 456, 789, 134]
const list = [123, 456, 789, 134, 123, 456, 789] // 缺少一个
const list1 = [123, 456, 789, 123, 456, 789] // 缺少两个，同一ID
const list2 = [123, 456, 789, 134, 123, 456] // 缺少两个，不同ID解法一：利用哈希表记下每个ID出现的次数
function getSingleNumber (list) {
let countMap = new Map()
for (let id of list) {
let count = countMap.get(id)
if (count) {
countMap.set(id, count + 1)
} else {
countMap.set(id, 1)
}
}
for (let [id, count] of countMap.entries()) {
if (count === 1) {
return id
}
}
}该解法的时间复杂度为O(N)，空间复杂度也为O(N)。
解法二：利用哈希表记下每个ID出现的次数(出现两次的删除)
ID为2的肯定不是故障机，可以不予考虑，即清除空间。
function getSingleNumber (list) {
let countMap = new Map()
for (let id of list) {
let count = countMap.get(id)
if (count) {
countMap.delete(id)
} else {
countMap.set(id, 1)
}
}
for (let [id, count] of countMap.entries()) {
if (count === 1) {
return id
}
}
}该解法的时间复杂度为O(N)，空间复杂度最好的情况下可以达到O(1)，最坏情况下仍然是O(N)。
解法三：“不变量”
originSum = originList.reduce((accumulator, currentValue) => accumulator + currentValue)
listSum = list.reduce((accumulator, currentValue) => accumulator + currentValue) = list.reduce((accumulator, currentValue) => accumulator + currentValue)
id = originSum - listSum // 134延伸：如果两台死机，这里需要分两种情况：第一种，两台是同一id；第二种，两台是不同的id。
originMult = originList.reduce((accumulator, currentValue) => accumulator * currentValue)
list2Sum = list2.reduce((accumulator, currentValue) => accumulator + currentValue)
list2Mult = list2.reduce((accumulator, currentValue) => accumulator * currentValue)
a + b = originSum - list2Sum // 923
a * b = originMult/list2Mult // 105726{a+b=923a∗b=105726 \begin{cases} a + b = 923 \\ a * b = 105726 \end{cases} {a+b=923a∗b=105726
function getSingleNumber (originList) {
let a, b
for (let i = 0; i < originList.length; i++ ) {
a = originList[i]
for (let j = i + 1; j < originList.length; j++ ) {
b = originList[j]
if (a + b === originSum - list2Sum && a * b === originMult/list2Mult) {
return [a, b]
}
}
}
}该解法的时间复杂度为O(N)，空间复杂度为O(1)
解法四：异或
x(i)=list[0]⊕list[1]⊕…⊕list[i] x(i) = list[0]⊕list[1]⊕…⊕list[i] x(i)=list[0]⊕list[1]⊕…⊕list[i]
function getSingleNumber (list) {
let xorResult = list[0]
for (let i = 1; i < list.length; i++) {
xorResult = xorResult ^ list[i]
}
return xorResult
}异或，$ a⊕b = (¬a ∧ b) ∨ (a ∧¬b) $ 如果a、b两个值不相同，则异或结果为1；如果a、b两个值相同，异或结果为0。异或满足交换律、结合律和自反性。 交换律：a ^ b = b ^ a 结合律：a ^ b ^ c = a ^ （b ^ c） = （a ^ b） ^ c，即d = a ^ b ^ c 可以推出 a = d ^ b ^ c 自反性：a ^ b ^ a = b
延伸：如果两台死机，这里需要分两种情况：第一种，两台是同一id；第二种，两台是不同的id。
getSingleNumber(list1) // 0，说明是两个相同ID
getSingleNumber(list2) // 915，说明是两个不同ID相同ID，(原集合的和 - 现集合的和) / 2
originSum = originList.reduce((accumulator, currentValue) => accumulator + currentValue)
list1Sum = list1.reduce((accumulator, currentValue) => accumulator + currentValue)
id = (originSum - list1Sum) / 2 // 134不相同ID
如果a⊕ba ⊕ ba⊕b 不等于0，那么这个异或值的二进制中某一位为1，显然a和b中有且仅有一个数的相同位异或结果也为1；我们把所有ID分两类，一类这位上为1，另一位这位上为0。再遍历相应列表，计算异或和，即可分别得到a和b的值。
originSum = originList.reduce((accumulator, currentValue) => accumulator + currentValue)
list2Sum = list2.reduce((accumulator, currentValue) => accumulator + currentValue)
diffNum = (originSum - list2Sum) // 923
function getSingleNumber (list) {
let firstOneIndex = getFirstOneIndex(diffNum)
let xorResult = [-1, -1]
for (let i = 0; i < list.length; i++) {
let binaryNum = list[i].toString(2)
if (binaryNum[binaryNum.length + firstOneIndex] === '0') {
xorResult[0] = xorResult[0] === -1 ? list[i] : xorResult[0] ^ list[i]
} else {
xorResult[1] = xorResult[1] === -1 ? list[i] : xorResult[1] ^ list[i]
}
}
return xorResult
}
// "1110011011" 从右到左，获取第一个1，用负数表示(下标从1开始)
function getFirstOneIndex (num) {
let binaryNum = num.toString(2)
return -(binaryNum.length - num.toString(2).lastIndexOf('1'))
}
getSingleNumber(list2) // [134, 789]该解法的时间复杂度为O(N)，空间复杂度为O(1)
腾讯云开发者
