牛客66道编程题——数组中只出现一次的数字

题目

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

方法一：利用python语言强大的功能

class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        tmp=[]
        for a in array:
            if a in tmp:
                tmp.remove(a)
            else:
                tmp.append(a)
        return tmp

方法二：哈希表法

class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        hashmap={}#定义一个哈希表为字典
        for a in array:#建立哈希表映射
            if str(a) in hashmap:
                hashmap[str(a)]+=1
            else:
                hashmap[str(a)]=1
        res=[]#建立一个返回表
        for i in hashmap.keys():
            if hashmap[i]==1:
                res.append(int(i))
        return res

方法三：异或法

当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的是唯一的数，因为成对出现的都抵消了。

class Solution:
    def FindNumsAppearOnce(self, array):
        if not array:
            return []
        # 对array中的数字进行异或运算
        tmp = 0
        for i in array:
            tmp ^= i
        # 获取tmp中最低位1的位置
        idx = 0
        while (tmp & 1) == 0:
            tmp >>= 1
            idx += 1
        a = b = 0
        for i in array:
            if self.isBit(i, idx):
                a ^= i
            else:
                b ^= i
        return [a, b]
 
    def isBit(self, num, idx):
        """
        判断num的二进制从低到高idx位是不是1
        :param num: 数字
        :param idx: 二进制从低到高位置
        :return: num的idx位是否为1
        """
        num = num >> idx
        return num & 1