题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

实现

思路1 Hashmap

第一想法就是建立哈希表来记录每个数字的出现次数。但不符合题目不使用额外空间的要求。

思路2 位运算

这里要用到异或（XOR）的三条性质：

  1. 0和二进制位做XOR运算，得到的仍然是这个二进制位；
  2. 相同的两个二进制位做XOR运算，结果为0；
  3. XOR满足交换律和结合律

因此我们可以对数组里所有数字进行异或运算，由于交换律和结合律的性质，可以理解成我们可以先计算所有相同数字异或的结果，也就是0。最后式子就变为 0 XOR 只出现一次的数，那么结果就是只出现一次的这个数字本身。

  1. class Solution:
  2.     def singleNumber(self, nums: List[int]) -> int:
  3.         for i in range(1, len(nums)):
  4.             nums[0] ^= nums[i]
  5.         return nums[0]

时间复杂度：. 只需要对数组遍历一次。
空间复杂度：136. 只出现一次的数字 - 图1