题目

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

方法

参考：https://blog.csdn.net/abc7845129630/article/details/52745029
时间复杂度：O(2n)

代码

function FindNumsAppearOnce (array) {
  // write code here
  // return list, 比如[a,b]，其中ab是出现一次的两个数字
  let result = 0
  array.forEach(item => {
    result ^= item
  })
  let arr1 = []
  let arr2 = []
  let first = FindFirstBit1(result)
  array.forEach(item => {
    if (iOfBitIs1(item, first)) {
      arr1.push(item)
    } else {
      arr2.push(item)
    }
  })
  let n1 = 0
  let n2 = 0
  arr1.forEach(item => {
    n1 ^= item
  })
  arr2.forEach(item => {
    n2 ^= item
  })
  return [n1, n2]
}

function FindFirstBit1 (n) {
  let i = 0
  while ((n & 1) !== 1) {
    n = n >> 1
    i++
  }
  return i
}

function iOfBitIs1 (n, i) {
  while (i--) n = n >> 1
  return n & 1
}