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

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？

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

示例 2:
輸入: [4,1,2,1,2]
輸出: 4

解答：

簡(jiǎn)單的方法可以用Counter方法計(jì)算出現(xiàn)次數(shù)，得到只出現(xiàn)一次的元素；
高級(jí)方法則使用異或，0異或任何數(shù)不變，任何數(shù)與自己異或?yàn)?。a⊕b⊕a=b。異或滿足加法結(jié)合律和交換律。而且這個(gè)方法不會(huì)使用外部額外空間。

class Solution:
    import collections    
    def singleNumber(self, nums):
        dic = collections.Counter(nums)
        for k,v in dic.items():
            if v == 1:
                return k
        
        """
        用異或:
        n=0
        for num in nums:
            n ^= num
        return n
        
        :type nums: List[int]
        :rtype: int
        """