【剑指Offer】40数组中只出现一次的数字

r囧r小猫 2022-05-12 13:58 138阅读 0赞

## 题目描述 ##

一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。

时间限制：1秒；空间限制：32768K；本题知识点：数组

## 解题思路 ##

### 思路一 ###

利用一个字典类型的数据dict1来存储 数字--次数 对，然后循环字典查找出现次数为一的数字，输出结果。

# -*- coding:utf-8 -*-
    class Solution:
        # 返回[a,b] 其中ab是出现一次的两个数字
        def FindNumsAppearOnce(self, array):
            # write code here
            dict1 = {} #新建字典用于存储 数字--个数
            for i in array:
                if str(i) in dict1: #将i转化为str型
                    dict1[str(i)] += 1
                else:
                    dict1[str(i)] = 1
            l = []
            for k in dict1.keys():
                if dict1[k] == 1:
                    l.append(int(k)) #将i转化为int型
            return l

### 思路二 ###

利用**异或**的思想来求解。一个数与它本身进行偶数次异或的结果为0，对原数组array全部数进行异或操作的结果是要求的ab两个数进行异或的结果。所以要做的就是通过某些操作将ab从异或结果中区分开啦，可以借助ab两数在二进制表达式下最右边的1的位置不同这个特点来区分，按照这个区别对原来的数组array分两组进行循环异或操作，便可以还原ab两个数。

Python程序：

# -*- coding:utf-8 -*-
    class Solution:
        # 返回[a,b] 其中ab是出现一次的两个数字
        def FindNumsAppearOnce(self, array):
            # write code here
            result = 0
            for obj in array:
                result ^= obj    #异或运算，剩下的是a,b不同的两个数的异或结果
            index = self.find_1_index(result)
            num1 ,num2 = 0, 0
            for obj in array:
                if self.is_bit_1(obj, index):
                    num1 ^= obj   #第N位为1的分为1组，这样能保证a,b分为两组
                else:
                    num2 ^= obj
            return num1, num2
         
        # 找到右边第一个为1的位置,右移和位与运算
        def find_1_index(self, digit):
            index = 0
            while not digit & 1:
                digit >>= 1
                index += 1
            return index
        
        # 判断某个数字的右边的第n位是否为1
        def is_bit_1(self, digit, n):
            digit >>= n
            return digit & 1     # 位与运算