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

这篇文章将为大家详细讲解有关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]

                       
                     

关于“LeetCode如何计算数组中数字出现的次数”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

原创文章,作者:奋斗,如若转载,请注明出处:https://blog.ytso.com/223474.html

(0)
上一篇 2022年1月6日
下一篇 2022年1月7日

相关推荐

发表回复

登录后才能评论