題目:

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

You must implement a solution with a linear runtime complexity and use only constant extra space.

給定一個陣列,裡面除了一個數以外其餘都兩兩相對,找出那單獨的數
ex:input:[4,1,2,1,2]=>output:4

一開始我的想法是遍歷然後用set紀錄

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        s=set()
        for i in nums:
            if i in s:
                s.remove(i)
            else:
                s.add(i) 
        return s.pop()

建立一個set,遍歷陣列的過程若值不在set內就加入set,在set內就將其移出set
因為除我們要的數以外都是兩兩相對
最後留在set的數便是我們要的single number
最後執行時間128ms(faster than 99.02%)

但我後來發現其實這樣解不是正規的
因為題目有規定解法的時間複雜度要O(n)且空間複雜度要O(1)
而上述的解雖然時間複雜度是O(n),但由於開了set紀錄所以空間複雜度來到O(n)
所以這個解法是不被接受的雖然會過

要找出不開新空間的解法,我百思不得其解
雖然在related topic中看到了位元運算(Bit Manipulations)
即以位元組為處理對象下去操作
但我仍不知道如何運用
最後看討論區才知道要用XOR(^)這個我從未見識過的運算子下去運算

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

XOR,即^,是對二進位型態的兩數的每一位進行比較
若該位兩數相同(1對1,0對0)則回傳0,兩數不同(1對0)則回傳1
因此兩個相同的數進行^運算會回傳0,因為兩數二進位每一位都相同
而一數和0進行^運算會回傳該數,因為每個1遇到0都會回傳1,每個0遇到0都會回傳0
我們利用這兩個性質就能迅速解開這題
因為兩兩一對的數終會化成0
0再跟single number進行^運算得到一樣的值
所以只要從第一項開始跟每一項行^運算最後就能得到single number(^適用交換律和結合律)
最後執行時間119ms(faster than 99.93%)

這是第二次在leetcode寫不出題目要求的解答
不過是自己完全不認識的語法讓挫折感沒那麼深
學起來以後遇到就會用了ouob

本題學習到的重點:位元運算(Bit Manipulations)之XOR
那我們下題見