jz056I.数组中数字出现的次数

题目链接

这个和之前做过的只出现一次的数字很像，区别在于只出现一次的数字有一个或者有两个。那我们是否可以利用解决只出现一个出现一次的数字中的方法呢，如果想要去利用，那么难点在于如何将数组分成两个子数组并且每个子数组分别包含了一个特殊的只出现一次的数字。我们还是从头到尾依此异或数组中的每个数字。由于有两个不一样的数字，得到的结果肯定不为0，也就是说这个结果数字的二进制表示中至少有一位为1。我们在结果中找到第一个为1的位置，记为第n位。现在我们以第n位是不是1为标准将原数组中的数字分成两个子数组，第一个子数组中每个数字的第n位都为1，而第二个子数组中的每个数字的第n位都为0。由于我们分组的标准是数字中的某一位是1还是0，那么出现了两次的数字肯定会被分配到同一个子数组。因为两个相同的数字的任意一位都是相同的，我们不可能把两个相同的数字分配到两个子数组中去，于是我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。我们已经知道如何在数组中找出唯一一个只出现一次的数字，因此，到此为止所有的问题都已经解决了。代码如下所示，这样做算法的时间复杂度是O（N），空间复杂度是O（1），满足题目要求。

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        tmp = reduce(lambda x, y: x ^ y, nums)
        div = 1
        while div & tmp == 0:
            div <<= 1
        a, b = 0, 0
        for n in nums:
            if div & n:
                a ^= n
            else:
                b ^= n
        return [a, b]