給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。
說(shuō)明：
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來(lái)實(shí)現(xiàn)嗎？
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4

• show the code:

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

• 此題可以聯(lián)想到很多方法，其中有暴力法：兩次遍歷，尋找只出現(xiàn)過(guò)一次的數(shù)，復(fù)雜度為
• 有哈希法，維護(hù)一個(gè)字典存儲(chǔ)之前出現(xiàn)過(guò)的數(shù)字，直到找出之前沒(méi)出現(xiàn)過(guò)的數(shù)字：即只出現(xiàn)一次的數(shù)字。時(shí)間和空間復(fù)雜度都為
• 但是題目要求線性時(shí)間復(fù)雜度而且不使用額外空間，所以以上兩種方法都不能AC，答案有一種位運(yùn)算的方法，即異或^，此符號(hào)表示兩個(gè)數(shù)字二進(jìn)制每位數(shù)相同的則為0，不同則為1，所以馬上推出兩個(gè)相同的數(shù)字異或的結(jié)果是0，0與任何數(shù)字異或的結(jié)果都是那個(gè)數(shù)字自身，所以我們只需要遍歷一遍即可得出結(jié)果。非常簡(jiǎn)單，也非常牛逼。