Thinking--快速找出故障机器(异或)

Thinking系列，旨在利用10分钟的时间传达一种可落地的编程思想。

假设一个机器仅存储一个标号为ID（数值）的记录，且该数据会保存备份(即，两个机器存储了同样的数据；类似于双节点部署)。

1. 在某个时间，如果得到一个数据文件ID的列表，是否能够快速找出这个列表中仅出现一次的ID？
2. 如果已知道有一台机器死机呢？如果两台呢？

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

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)

解法四：异或

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

如果

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)