剑指40-数组中只出现一次的数字

Posted on | In |

题目描述

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

  • 从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或的结果。因为其他数字都出现两次，在异或中全部抵消了。由于这两个数字肯定不一样，那么异或的结果肯定不为0，也就是说在这个结果数字的二进制表示中至少有一位为1.我们在结果数字中找到第一个为1的位的位置，记为第k位。
  • 现在我们以第k位是不是1为标准把原数组中的数字分成两个子数组。出现了两次的数字肯定被分配到同一个子数组中，因为两个相同的数字的任意一位都是相同的。不可能把两个相同的数字分配到两个子数组中去。
  • 每个子数组都包含了一个只出现一次的数字，而其他数字都出现了两次，分别对子数组所有元素求异或，就把那个只出现一次的数找出来了。
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
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        def k_bit_0(num, k):
            # 本函数查看num的第k个比特位是否是1
            # k为0,1,2,...
            while k > 0:
                k -= 1
                num = num>>1
            return num&1
        
        def first_bit_1(num):
            # 本函数返回数字二进制位从最低位开始的第一个非0位置
            # k为0,1,2,...
            k = 0
            while True:
                if num&1 == 0:
                    num = num>>1
                    k += 1
                else:
                    break
            return k        

        # 所有数求异或得到xor_all
        xor_all = 0
        for num in array:
            xor_all ^= num
        # 找到xor_all的从最低位开始的第一个二进制1的位置
        k = first_bit_1(xor_all)

        a, b = 0, 0
        for num in array:
            if k_bit_0(num, k): 
                # 根据第k个二进制位是否是1，可以将所有数字分为两类，两个只出现一次的数肯定不在同一类，因为第k二进制位肯定不一样。
                #而且每一类除了只出现一次的数，其它数都是成对出现。
                #那么，两类分别对其所有元素求异或，则异或结果是那个只出现一次的数。
                a ^= num
            else:
                b ^= num
        return [a, b]

遍历数组，用字典统计每个元素的频度。然后把字典里频度为1的数找出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        mydict = {}
        for num in array:
            if mydict.has_key(num):
                mydict[num] += 1
            else:
                mydict[num] = 1
        mylist = []
        for k, v in mydict.items():
            if v == 1:
                mylist.append(k)
        return mylist