剑指offer - 找到数组中两个只出现一次的数

题目描述

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

思路

这个题我本来打算用暴力来解决的，弄一个dictionary，然后对每个数计数。

 

 

优化

空间复杂度为O(1)

用异或，相同数字的异或为0，0与任何数异或 为任何数。 

这样所有数异或的结果，为那两个只出现一次的数

然后根据这个异或结果，找出两个数 二进制位不同的一位（只要找一位就好）

根据这个二进制位分组，为0的在一组，为1的在一组。这样两个数字肯定被分到了不同组。而每一组里面的数字，只有一个只出现一次的数，其余数都出现两次.....不用说了，分别异或

class Solution:
    def FindNumsAppearOnce(self, array):
        if len(array)<2:
            return False
        num = array[0] ^ array[1]
        for i in range(2,len(array)):
            num ^= array[i]
        
        # 找到二进制位不同的一位，只需要找出来一位就行
        i = 1
        while num%2 == 0:
            num = int(num//2)
            i += 1
        
        # 按照上面找到的二进制位分组异或
        num1 = 0
        num2 = 0
        for num in array:
            if num%(2**i) == (2**(i-1)):
                num1 ^= num
            else:
                num2 ^= num
        return num1,num2