Leetcode: Sword finger offer 56 - I. number of occurrences in the array [grouping XOR]

analysis

If it all happens twice , Only one appears at a time
Then the one that appears at a time is all XOR

But there are two things that happen at once , So these two goals are all exclusive or a and b Exclusive or of res
We find res One of them is 1 To distinguish a and b

Then the other same words will definitely be divided into the same group
In this way, the grouping XOR obtains two results, that is, the two appear 1 The number of times

ac code

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        #  Group XOR 

        # 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]

summary

Several even numbers , An odd number appears , Eliminate even occurrences of by XOR （ Magic XOR ）
Pay attention to the reduce Usage of ：reduce(func, list)