VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > temp > 简明python教程 >
  • LeetCode 面试题56 - I. 数组中数字出现的次数 | Python

面试题56 - I. 数组中数字出现的次数


题目


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

示例 1:

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]

示例 2:

输入:nums = [1,2,10,4,1,4,3,3]
输出:[2,10] 或 [10,2]

限制:

  • 2 <= nums <= 10000

解题思路


思路:异或,位运算

先说下异或的性质:二进制位同一位相同则为 0,不同则为 1。

再说说一下异或的规律:

  • 若两数值相同,两者的异或结果为 0,(即是任何数与自身异或结果为 0)
  • 任何数与 0 异或结果为本身

同时异或是满足交换律,结合律的(数学符合:⊕)

  • 交换律: a ⊕ b = b ⊕ a
  • 结合律: a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c

回来看本题,题目说明,【整型数组 nums 中,除两个数字之外,其他数字都出现了两次】。那么根据交换律、结合律将相同数字进行异或运算,那么相同数字都会变为 0,再根据第二条规律,那么剩下的出现一次的数字。

在这里主要需要实现的如何确保将数组分成两组,使得:

  • 只出现一次的数字,在不同的两组;
  • 相同的数组出现在相同的组。

只有这样,每组进行异或运算的时候,最终才会剩下单独的数字。那么该如何进行分组?特别是如何将两个不同的数字分到不同的组?

分组描述

具体实现代码如下。

代码实现


class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        res = 0
        # 全员进行异或
        for num in nums:
            res ^= num
        
        # 找出不为 0 的最低位
        # & 位运算的使用
        div = 1
        while (div & res == 0):
            div <<= 1
        
        # 进行分组
        p, q = 0, 0
        for num in nums:
            if num & div:
                p ^= num
            else:
                q ^= num
            
        return [p, q]

实现结果


实现结果


以上就是使用异或,位运算的思路,解决《面试题56 - I. 数组中数字出现的次数》问题的主要内容,题目主要的难度在于如何对数组进行分组,然后根据异或的规律性质进行求解。


欢迎关注微信公众号《书所集录》


相关教程