数组中只出现一次的两个数字

题目链接

• 牛客网

题目描述

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

数据范围：数组长度 2≤n≤1000，数组中每个数的大小 0<val≤1000000 要求：空间复杂度O(1)，时间复杂度O(n)

提示：输出时按非降序排列。

示例：

#输入：
[1,4,1,6]
#返回值：
[4,6]
#说明：
#返回的结果中较小的数排在前面

刷题思路

方案一：

• 对数组进行排序（升序）
• 按照在开头、在中间、在结尾，三种情况分条件比较

有点投机取巧，可以使用sort进行排序，也可以使用时间复杂度最低的快速排序

方案二：

• 利用哈希表，统计出现次数
• 遍历哈希表，找出只出现一次的，升序输出

方案三：

• 利用位运算，即：异或运算（同0异1）

异或运算不常用，有点难度

代码实现

/**
 * 先排序，利用出现一次特性
 */
function findNumsAppearOnceOne(array) {
  // 数组中元素要么出现一次，要么出现两次，可以先对元素进行排序有点偷懒的样子
  array = array.sort((a, b) => a - b)
  const len = array.length
  // 此时的 数组已经进过排序
  const onceResult = []

  // 在开头
  if (array[0] !== array[1]) {
    onceResult.push(array[0])
  }
  // 在中间
  for (let index = 1; index < len - 1; index++) {
    if (array[index - 1] !== array[index] && array[index] !== array[index + 1]) {
      onceResult.push(array[index])
    }
  }
  // 在结尾
  if (array[array.length - 1] !== array[array.length - 2]) {
    onceResult.push(array[array.length - 1])
  }
  return onceResult
}

/**
 * 利用Map统计出现次数
 */
function findNumsAppearOnceTwo(array) {
  const resMap = new Map()
  // 统计
  for (const value of array) {
    if (resMap.has(value)) {
      resMap.set(value, resMap.get(value) + 1)
    }
    else {
      resMap.set(value, 1)
    }
  }

  const onceResult = []
  // 找出出现一次的
  for (const [key, value] of resMap) {
    if (value === 1) {
      onceResult.push(key)
    }
  }
  // 按从小到大输出
  return onceResult.sort((a, b) => a - b)
}

/**
 * 利用异或运算
 */
function findNumsAppearOnceThree(array) {
  let res1 = 0
  let res2 = 0
  let temp = 0
  // 遍历数组得到a^b
  for (let i = 0; i < array.length; i++) { temp ^= array[i] }
  let k = 1

  // 找到两个数不相同的第一位
  while ((k & temp) === 0) { k <<= 1 }
  for (let i = 0; i < array.length; i++) {
    // 遍历数组，对每个数分类
    if ((k & array[i]) === 0) { res1 ^= array[i] }
    else { res2 ^= array[i] }
  }

  // 升序
  return res1 > res2 ? [res2, res1] : [res1, res2]
}

console.log(findNumsAppearOnceOne([1, 2, 3, 3, 2, 9]))
console.log(findNumsAppearOnceTwo([1, 2, 3, 3, 2, 9]))
console.log(findNumsAppearOnceThree([1, 2, 3, 3, 2, 9]))

一些建议

• 熟练使用基本数组排序
• Map结构重要，常用api需要熟悉
• 位运算是数学问题，可以了解