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

Solutions

  第一种方法是很不优雅的方法,利用字典统计个数。

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        arr_dict = {}
        for item in array:
            if item in arr_dict:
                arr_dict[item] += 1
            else:
                arr_dict[item] = 1
        res = []
        for item in array:
            if item in arr_dict and arr_dict[item] == 1:
                res.append(item)
        return res[0], res[1]
# 运行时间:34ms
# 占用内存:5624k

  第二种方法是书上的解法,采用异或的方式,用 0 跟所有的数异或后,肯定结果不为 0,然后找到结果中右起的第一个 1 的位置,通过这个位置上是否为 1 再次遍历数组后可以将数组分成分别以两个单次出现的数为相同特征的子数组,分别异或得到结果即可(0 异或任何数不变)。

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        if array is None or len(array) < 2:
            return None
        xor = 0
        for item in array:
            xor ^= item
        idxBit = self.FindFirstBitIs1(xor)
        
        res1, res2 = 0, 0
        
        for item in array:
            if self.IsBit1(item, idxBit):
                res1 ^= item
            else:
                res2 ^= item
        return res1, res2
    
    def FindFirstBitIs1(self, num):
        idxBit = 0
        while num & 1 == 0 and idxBit < 32:
            num >>= 1
            idxBit += 1
        return idxBit
    
    def IsBit1(self, num, idxBit):
        num >>= idxBit
        return num & 1
# 运行时间:42ms
# 占用内存:6968k

  第三种方法是利用 Python 的现成库 collections 中的 Counter 类。

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        from collections import Counter

        res=Counter(array).most_common()[-2:]
        return list(map(lambda x:x[0],res))

References

  1. 040. 数组中只出现一次的数字