跳至主要內容

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


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

题目链接

题目描述

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

数据范围:数组长度 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需要熟悉
  • 位运算是数学问题,可以了解