題目

給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。

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

方法一：字典

• dict 用于記錄數(shù)組中每個數(shù)字的出現(xiàn)次數(shù)
• 循環(huán)遍歷，計算每個數(shù)字的出現(xiàn)次數(shù)
• 循環(huán)遍歷字典的鍵值，根據(jù)題目只有一個數(shù)字出現(xiàn)一次，那么當(dāng)出現(xiàn)值為 1 時，該值對應(yīng)的鍵即為我們需要找的數(shù)字

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

方法二：位運算

使用位運算的話就不需使用額外空間
根據(jù)異或運算的定義和題目，我們可以假設(shè)出現(xiàn)兩次的元素為 a1,..., am 而出現(xiàn)一次的元素為 am+1。對所有的元素進(jìn)行異或操作，那么
(a1 ^ a1) ^ (a2 ^ a2) ^ ... ^ am+1
= 0 ^ 0 ^ ... ^ am+1
= am+1
所以根據(jù)此計算可知全部元素異或運算的結(jié)果即為數(shù)組中只出現(xiàn)一次的元素值

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)

相關(guān)知識

• 異或運算： ^
  x ^ 0 = x
  x ^ x = 0

• lambda 函數(shù)： lambda arguments : expression
  argument： 參數(shù)
  expression： 表達(dá)式

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

• reduce 函數(shù)： reduce(function, iterable[, initializer])
  對參數(shù)序列中元素進(jìn)行累積
  function： 函數(shù)
  iterable： 可迭代對象
  initializer： 初始參數(shù)（可選）

參考

代碼相關(guān)：https://leetcode.cn/problems/single-number/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-solution/
lambda 函數(shù)：https://www.w3school.com.cn/python/python_lambda.asp
reduce 函數(shù)：