Python程式設計題22--隻出現一次的數字

題目

給定一個非空整數清單，除了某個元素隻出現一次以外，其餘每個元素均出現兩次。請找出那個隻出現了一次的元素。

注意：除了定義的傳回結果變量外，不允許使用額外空間，并且不允許使用程式設計語言的内置函數。

例如：

給定一個清單：[4, 1, 2, 1, 2]，傳回結果：4

給定一個清單：[2, 2, 1]，傳回結果：1

實作思路

• 通過 ​

  ​位運算​

  ​ 來實作，設定一個傳回值res，預設值為0
• 周遊清單元素，每次均與res進行異或運算
• 清單中隻有1個元素出現一次，其餘元素均出現兩次，相同元素異或的結果為0，是以最終的結果res就是這個隻出現一次的元素

在二進制的異或運算中，例如a=12，b=7，那麼a異或b的結果c計算如下：

a = 0 0 0 0 1 1 0 0

b = 0 0 0 0 0 1 1 1

c = 0 0 0 0 1 0 1 1 （相同位的值為0，不同為1）

是以我們可以看出：0異或任一個數a，其結果為 a；任一數a異或自己，也就是 a異或a，其結果為 0

代碼實作

def singleNumber(nums):
    res = 0
    for num in nums: 
        res = res ^ num
    return res
      

作者：​​wintest​​