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]