查找只出现一次的数字

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

说明：

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

示例 1:

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

示例 2:

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

解题思路

1. 采用list.count == 1来找出一个数字

   class Solution:
       def singleNumber(self, nums: List[int]) -> int:
           for i in nums:
               if nums.count(i) == 1:
                   return i
   

   最终结果会超时

2. 采用列表，遍历nums到每一个元素；如果元素是在list中没有出现过，则将它添加到list中；反之如果元素已经在列表中，则删除它。

   class Solution:
       def singleNumber(self, nums: List[int]) -> int:
           list = []
           for i in nums:
               if i not in list:
                   list.append(i)
               else:
                   list.remove(i)
           return list[0]
   

   取list的第一个数据

3. 采用hash表，操作和方法2一致。

   class Solution:
       def singleNumber(self, nums: List[int]) -> int:
           hash_table = {}
           for i in nums:
               try:
                   hash_table.pop(i)
               except:
                   hash_table[i] = 1
           return hash_table.popitem()[0]
   

4. 位运算

   概念：

   ​ 如果我们对0和二进制位做XOR运算，得到的是这个二进制位

   ​ a⊕0=a

   ​ 如果我们对相同的二进制位做XOR运算，返回的结果是0

   ​ a⊕a=0

   ​ XOR满足交换律和结合律

   ​ a⊕b⊕a=(a⊕a)⊕b=0⊕b=b

   因此，我们只需要将所有的数字进行XOR运算，就得到那个唯一的数字了。

   class Solution:
       def singleNumber(self, nums: List[int]) -> int:
           num = 0
           for i in nums:
               num ^= i
           return num