当前位置:网站首页>剑指 Offer 56 - I. 数组中数字出现的次数

剑指 Offer 56 - I. 数组中数字出现的次数

2022-08-06 07:57:35愈努力俞幸运

剑指 Offer 56 - I. 数组中数字出现的次数icon-default.png?t=M666https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
 

首先介绍异或的概念

异或_百度百科 (baidu.com)icon-default.png?t=M666https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fr=aladdin 

暴力代码,采用字典的标记出现几次

class Solution:
    def singleNumbers(self, nums):
        dic={}
        res=[]
        for i in nums:
            dic[i]=0
        for i in nums:
            dic[i]+=1
        for i in nums:
            if dic[i]==1:
                res.append(i)
        return res

 

 

def singleNumber(self, nums: List[int]) -> List[int]:
    x = 0
    for num in nums:  # 1. 遍历 nums 执行异或运算
        x ^= num      
    return x;         # 2. 返回出现一次的数字 x

 

怎么把它们分成一个包含x,另一个包含y呢?

 

 

 

while z & m == 0: # m 循环左移一位,直到 z & m != 0
    m <<= 1

 

for num in nums:
    if num & m: x ^= num  # 若 num & m != 0 , 划分至子数组 1 ,执行遍历异或
    else: y ^= num        # 若 num & m == 0 , 划分至子数组 2 ,执行遍历异或
return x, y               # 遍历异或完毕,返回只出现一次的数字 x 和 y

  1. 返回值
  • 返回只出现一次的数字 x, y 即可。

 

class Solution:
    def singleNumbers(self, nums):
        z=0
        for i in nums:
            z^=i
        m=1
        while z&m==0:
            m<<=1
        x,y=0,0
        for i in nums:
            if i & m==0:
                x^=i
            else: y^=i
        return [x,y]

 

 

K神的返回值可能格式上有问题,K神返回的是x,y的元组 

 

 

 

 

 

 

 

 

 

原网站

版权声明
本文为[愈努力俞幸运]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_37891604/article/details/126187560

随机推荐