LeetCode 136. 只出现一次的数字

题目

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

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

方法一：字典

• dict 用于记录数组中每个数字的出现次数
• 循环遍历，计算每个数字的出现次数
• 循环遍历字典的键值，根据题目只有一个数字出现一次，那么当出现值为 1 时，该值对应的键即为我们需要找的数字

class Solution(object):
    def singleNumber(self, nums):
        dict = {}
        for i in range(len(nums)):
            if nums[i] not in dict:
                dict[nums[i]] = 1
            else:
                dict[nums[i]] += 1
        for key, val in dict.items():
            if val == 1:
                return key

方法二：位运算

使用位运算的话就不需使用额外空间
根据异或运算的定义和题目，我们可以假设出现两次的元素为 a1,..., am 而出现一次的元素为 am+1。对所有的元素进行异或操作，那么
(a1 ^ a1) ^ (a2 ^ a2) ^ ... ^ am+1
= 0 ^ 0 ^ ... ^ am+1
= am+1
所以根据此计算可知全部元素异或运算的结果即为数组中只出现一次的元素值

class Solution(object):
    def singleNumber(self, nums):
        result = 0
        for num in nums:
            result ^= num
        return result

简化版

class Solution(object):
    def singleNumber(self, nums):
        return reduce(lambda x, y: x^y, nums)

相关知识

• 异或运算： ^
  x ^ 0 = x
  x ^ x = 0

• lambda 函数： lambda arguments : expression
  argument： 参数
  expression： 表达式

x = lambda a : a + 10
print(x(5))

• reduce 函数： reduce(function, iterable[, initializer])
  对参数序列中元素进行累积
  function： 函数
  iterable： 可迭代对象
  initializer： 初始参数（可选）

参考

代码相关：https://leetcode.cn/problems/single-number/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-solution/
lambda 函数：https://www.w3school.com.cn/python/python_lambda.asp
reduce 函数：