Skip to main content

2-25 136.只出现一次的数字

Date：2022-02-27 17:45:52

😄 😕 😟 三个小表情表示题目难度：简单 中等 困难

题目：136. 只出现一次的数字 [简单😄 ]​

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明​

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例​

示例1

输入: [2,2,1]
输出: 1

示例2

输入: [4,1,2,1,2]
输出: 4

分析​

比较常规想到的解法：

  • [哈希表] 遍历数组，用一个哈希表存每个数出现的次数，再遍历一遍，拿到次数为1的就是出现一次的元素
  • [集合] 遍历数组，用一个集合存数据，规则为：1.如果该元素存在，则删除 2.如果不存在，则加入，那么最后剩余的元素，就是出现一次的元素
  • [求和] 先求数组之和s1，再遍历数组，用一个集合存所有元素，再将集合元素求和s2，那么s2 - s1就是出现一次的元素（该解法前提为元素是纯数字）

以上三个方法虽然时间复杂度满足，但都是需要 O(n) 的辅助空间，如果不用辅助空间，则这里可以采用 位运算 ，推理过程：

首先需要知道位运算三个性质：

  • 一个数和0作位运算，结果为该数
  • 一个数和自身作位运算，结果为0
  • 满足交换律和结合律：
  • 即 a⊕b⊕a = b⊕a⊕a = b⊕(a⊕a) = b

假设有m个元素出现两次，1个元素出现一次，那么共有2m+1个元素，这2m+1个元素异或结果为：

(a1⊕a1)⊕(a2⊕a2) ... ⊕((m-1)⊕(m-1))⊕(m+1) = m+1

m+1就是出现一次的元素

题解​

function main() {
  // const arr = [2, 2, 1]
  const arr = [4, 1, 2, 1, 2]
  console.log('[singleNumber]:', singleNumber(arr))
}

main()

function singleNumber(arr: number[]): number {
  let res = 0
  for (let i = 0; i < arr.length; ++i) {
    res ^= arr[i]
  }

  return res
}