数组中数字出现的次数

来源: Leetcode-数组中数字出现的次数

1. 解题思路

• 异或
• 异或满足交换律, 即 a ^ b ^ c = a ^ c ^ b

2. 代码

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        ret = 0  # 所有数字异或的结果
        a = 0
        b = 0
        for n in nums:
            ret ^= n
        # 找到第一位不是0的
        h = 1
        while(ret & h == 0):
            h <<= 1
        for n in nums:
            # 根据该位是否为0将其分为两组
            if (h & n == 0):
                a ^= n
            else:
                b ^= n

        return [a, b]