数组中只出现一次的数字--python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#一个整型数组中除了两个数字之外，其他数字都出现了两次。找到这个两个只出现一次是数字。要求时间复杂度O(n),空间复杂度O(1)
#思路1：字典，以数组中的数字为键，出现次数为值，最后找到值为1对应的键
def findOnceNum(arr):
    if len(arr) < 2:
        return None
    dict, res = {}, []
    for i in arr:
        dict[i] = dict.get(i, 0) + 1
    for key in dict:
        if dict[key] == 1:
            res.append(key)
    return res

#思路2：异或思想,任何一个数字异或它自己都是0
#用异或求解。异或运算的性质：任何一个数字异或它自己都等于0 。如果数组中只有一个数字出现过一次，其余数字都出现了两次；这样的话如果我们从头到尾依次异或数组中的每一个数字，
# 那么最终的结果刚好是那个只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。如果能够把原数组分为两个子数组，在每个子数组中，包含一个只出现一次的数字，
# 而其它数字都出现两次。在两个子数组中分别求出这两个只出现一次的数字。 还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。
# 因为其它数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0 ，也就是说在这个结果数字的二进制表示中至少就有一位为1 。
# 我们在结果数字中找到第一个为1的位的位置，记为第N 位。现在我们以第N 位是不是1 为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N 位都为1 ，
# 而第二个子数组的每个数字的第N 位都为0 。现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其它数字都出现了两次。因此到此为止，所有的问题我们都已经解决。
def findOnceNum(arr):
    if len(arr) < 2:
        return None
    tmp, index = 0, 1  # 得到最终的结果，两个只出现一次的数字异或的结果
    for i in arr:
        tmp = tmp ^ i
    # 在结果数字中找到第一个为1的位
    while tmp & index == 0:
        index = index << 1
    res1, res2 = 0, 0
    for num in arr:
        # 将原始数组分为两个子数组
        if num & index == 0:
            res1 = res1 ^ num
        else:
            res2 = res2 ^ num
    return [res1, res2]

# print(findOnceNum([2,4,3,6,3,2,5,5]))