leetcode：剑指 Offer 56 - I. 数组中数字出现的次数【分组异或】

分析

如果全都是两次出现，只有一个一次出现
那么一次出现的那个就是全部异或

但此时有两个一次出现的，所以全部异或的就是这两个目标a和b的异或res
我们找到res中某一位是1的来区分a和b

然后其他相同的话肯定会分到同一组
这样就是分组异或得到两个结果就是那两个出现1次的数

ac code

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        # 分组异或

        # reduce(func, list)
        res = reduce(lambda x, y: x ^ y, nums)
        
        # find a bit to divide these two nums
        div = 1
        while div & res == 0:
            div <<= 1
        
        a, b = 0, 0
        # two groups and xor
        for num in nums:
            if num & div:
                a ^= num
            else:
                b ^= num
        
        return [a, b]

总结

若干出现偶数，一个出现奇数，通过异或消除偶数次出现的（神奇的异或）
注意一下reduce的用法：reduce(func, list)