leetcode (力扣) 260. 隻出現一次的數字 III (哈希表) (異或位運算)

題目在這​​:https://leetcode-cn.com/problems/single-number-iii/​​

法一（哈希表）：

直接使用哈希表。元素值為key 其出現的次數為value。直接周遊哈希表輸出value為1的key。

完整代碼:

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        from collections import  Counter

        hs = Counter(nums)
        res = []
        for i in hs:
            if hs[i] == 1:
                res.append(i)
        return      

法二 (異或位運算)：

異或運算:

a ^ a = 0

a ^ b = 1

即相同為0，不同為1. 這裡的相同不同是在二進制下做的對位比較。

我們對整個字元串進行異或，隻會剩下兩個隻出現了一次的字元的異或結果。

比如字元串: aabbcddeff aa異或為0 bb異或為0.。。。。。最後隻會剩下c和e進行異或。我們拿到這個結果記為res。

我們重新周遊原字元串，使用某種方法對原來的字元串進行分類。是他們分成兩撥。這兩個隻出現一次的字母分别在不同的批次裡。 即 A批次隻有一個隻出現了一次的數字，其他都是一對一對的。B批同理。

那這個方法是什麼呢？

上面說過，異或二進制對位不同的情況下為1。由于結果res為兩個不同數字異或出來的結果，是以res的二進制數必然有1。我們需要找到這個數字1從右邊數的位置，設一個數 h = 1讓他和res不斷的進行 與 操作。 如果為0則讓h往左挪一位。右邊空出來的地方補0，這樣操作下去的結果就是h會變成 1後面跟着N個0。即此時已經找到了右邊數的第一個1的位置。

再簡單點說~這個所找到的1的位置，是兩個隻出現一次的數，這倆數在該位置上必然是一個為0一個為·1，異或出來就是結果為1.

是以重新周遊數組，讓h和每一個數進行 與 操作，必然可以将兩個隻出現一次的數分到不同的組中，其他一對一對的數配置設定的如何我們不考慮，隻要能吧兩個隻出現一次的數分開即可。

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        res = 0

        for i in nums:
            res ^= i # 将整個字元串異或
        h = 1
        while res & h == 0:
            h  = h << 1 # 找到從右邊數第一個出現的1的位置
        a = 0
        b = 0

        for j in nums:
            if h & j == 0: # 分類
                a ^= j
            else:
                b ^= j
        return [a,b]