题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
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))