LeetCode如何计算数组中数字出现的次数

题目描述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n)，空间复杂度是 O(1)。

• 2 <= nums.length <= 10000

题目样例

示例

• 输入：nums = [4,1,4,6]

• 输出：[1,6] 或 [6,1]

• 输入：nums = [1,2,10,4,1,4,3,3]

• 输出：[2,10] 或 [10,2]

题目思考

1. 如果其他数字都出现两次, 只有一个数字出现一次如何解决?
2. 如何做到空间复杂度是 O(1)?

解决方案

思路

• 分析题目, 相信大家都能想到计数字典的方案, 就是记录每个数字的次数, 然后找次数为 1 的数字, 但这样空间复杂度为 O(N), 不满足要求
• 我们先来分析一个简化问题: 如果其他数字都出现两次, 只有一个数字出现一次如何解决?
• 这个问题估计不少同学都见过, 一个很巧妙的做法是 异或所有数字, 因为两个相同数字的异或结果一定为 0, 所以最终异或的结果一定是那个出现一次的数字
• 那针对这道题, 还可以利用异或思路吗?
• 答案是肯定的, 假设我们还是异或所有数字, 那么 最终异或出来的值等价于那两个出现一次的数字的异或结果, 因为其他出现两次的数字异或都是 0, 对最终异或结果没有影响.
• 而异或结果中的某一位 1, 代表这两个数字在这一位上的取值不同, 一个是 0, 一个是 1
• 我们可以利用这一点, 将原数组分为两类, 一类是该位为 1 的, 一类是该位为 0 的. 对于出现两次的数字而言, 它们肯定落在同一类里面; 而对于这两个出现一次的数字, 它们被分属在两个不同类中.
• 这样问题就转换成了上面描述的简化问题, 只需要对这两类分别求出它们的异或结果, 自然就是对应两个出现一次的数字了~
• 最后一个问题: 如何求异或结果 xor 的某一位 1 呢?
• 我们可以利用循环, mask 从 1 开始, 判断 xor 的这一位是否为 1, 是的话就跳出循环, 否则 mask 左移一位, 直到超出 xor
• 当然还有更简单的做法, 利用树状数组的 lowbit, 也即 xor & -xor, 直接就能求得最低位的 1 对应的数字, 这个大家手动模拟下补码就知道是为什么了
• 下面代码对必要的步骤有详细的解释, 方便大家理解

复杂度

• 时间复杂度 O(N): 遍历两遍数组
• 空间复杂度 O(1): 只使用了几个变量

代码

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        # 先拿到所有数字的异或结果, 该结果一定至少有一位是1, 否则就不可能有两个出现一次的数字
        xor = 0
        for n in nums:
            xor ^= n
        # 然后随便针对异或结果的某一位1, 将原数组分为两类, 自然两个出现一次的数字就会分别落在不同类里面, 否则其异或结果的这一位不可能是1
        # 这里直接利用树状数组的lowbit(即原来的数字的最低位的1)
        mask = xor & -xor
        a, b = 0, 0
        for n in nums:
            if n & mask:
                # 如果数字的这一位是1, 归为一类, 求它们的异或值, 即为其中一个出现一次的数
                a ^= n
            else:
                # 如果数字的这一位是0, 归为另一类, 求它们的异或值, 即为另一个出现一次的数
                b ^= n
        return [a, b]