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

题目描述

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

时间限制：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     # 位与运算