前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Thinking--快速找出故障机器(异或)

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

作者头像
奋飛
发布2019-08-14 18:00:36
4240
发布2019-08-14 18:00:36
举报
文章被收录于专栏:Super 前端

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

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

  1. 在某个时间,如果得到一个数据文件ID的列表,是否能够快速找出这个列表中仅出现一次的ID?
  2. 如果已知道有一台机器死机呢?如果两台呢?
代码语言:javascript
复制
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出现的次数

代码语言:javascript
复制
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的肯定不是故障机,可以不予考虑,即清除空间。

代码语言:javascript
复制
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)。

解法三:“不变量”

代码语言:javascript
复制
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。

代码语言:javascript
复制
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​

代码语言:javascript
复制
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]

代码语言:javascript
复制
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。

代码语言:javascript
复制
getSingleNumber(list1)	// 0,说明是两个相同ID
getSingleNumber(list2)	// 915,说明是两个不同ID

相同ID,(原集合的和 - 现集合的和) / 2

代码语言:javascript
复制
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的值。

代码语言:javascript
复制
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)

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年06月23日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 解法一:利用哈希表记下每个ID出现的次数
  • 解法二:利用哈希表记下每个ID出现的次数(出现两次的删除)
  • 解法三:“不变量”
  • 解法四:异或
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档