『哈希表；位运算』只出现一次的数字136

题目相关

• 原题链接：136. 只出现一次的数字 - 力扣（LeetCode）
• 涉及知识：哈希表，位运算
• 题目难度：★

题目解读

显而易见，一个字典即可搞定。然而此题还有一种相当巧妙的解法是位运算，具体如：

• 如果我们对 0 和二进制位做 XOR 运算，得到的仍然是这个二进制位
  
• 如果我们对相同的二进制位做 XOR 运算，返回的结果是 0
  
• XOR 满足交换律和结合律
  

Python相关

无

具体实现

哈希表实现如下：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        dic = {}
        for num in nums:
            if num not in dic:
                dic[num] = 1
            else:
                del dic[num]
        return list(dic.keys())[0]

位运算实现如下：

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = 0
        for i in nums:
            a ^= i
        return a