Leetcode題解 Python： 四月挑戰DAY1 Single Number

「Given a non-empty array of integers, every element appears twice except for one. Find that single one.」

給一串非空整數字串列，每個元素會重複兩次，只有一個只出現一次，找出來。

這題非常簡單，一開始就有各種解法。不過我當作可能重複不只兩次，用這樣的前提寫出：

class Solution:    
    def singleNumber(self, nums: List[int]) -> int:
        memo = {}
        memo2 = {}
        for num in nums:
            if num in memo2:
                continue                    
            else:
                if num in memo:
                    del memo[num]
                    memo2[num] = 0
                    continue
                memo[num] = num   
        
        for key in memo: return memo[key]

我在想，有沒有甚麼只循環過一遍就能得到解法？不要有跑完N兩次或以上。看了前段班解法，回頭看題目才知道頂多重複兩次。(又再一次沒有看清楚題目

我的解法也只會跑過一次N。


偷看大神的解答，覺得這個相當精巧。

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

運用「 ^= 」，重複的數字會重複兩次，於是會抵消掉，最後的值會等於只出現一次的數字。這方法不需要排序，也不用比較，也只需要遍歷串列過一次。