Skip to main content

只出现一次的数字

Tips

题目类型: 位运算

相关题目:

题目​

给定一个非空整数数组, 除了某个元素只出现一次以外, 其余每个元素均出现两次. 找出那个只出现了一次的元素. 你必须设计并实现线性时间复杂度的算法来解决此问题, 且该算法只使用常量额外空间.

示例
输入: [2, 2, 1]

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

输出: 4

题解​

使用按位异或, 关于按位异或可访问 位运算的一些技巧.

以 [4, 1, 2, 1, 2] 为例,

  • 4 ^ 1 = 5
  • 5 ^ 2 = 7
  • 7 ^ 1 = 6
  • 6 ^ 2 = 4
// 按位异或(XOR)
var singleNumber = function (nums) {
  return nums.reduce((acc, val) => acc ^ val)
}