题目

数组中只出现一次的两个数字

一、哈希表+队列

简单明了，哈希表+队列

def find_num_appera_once_1(arr):
    if not arr:
        return None
    d = {}
    queue = []
    for num in arr:
        if num not in d:
            d[num] = 1
            queue.append(num)
        else:
            if d[num] == 1:
                queue.remove(num)
            d[num] += 1
    return queue

二、异或

首先说一个结论：任何数和自己异或=0
看一下这个数组的特点，除了我们要找的两个数，其他数都有两个！
如果我们把这个数组的所有数异或，那结果=我们要找的两个数的异或值。例如：
【1，2，2，4，3，1】
1 ^ 2 ^ 2 ^ 4 ^ 3 ^ 1 = 4 ^ 3 = 7
（为什么4 ^ 3 = 7
4 的二进制： 100
3 的二进制： 011
按位求异或： 111

111的十进制： 7
）

但是根据整个数组的异或值7，我们判断不出来是4和3。
如果能够把数组分成两个部分来看，相同的数字全部放到一边，不相同的这两个数字不能放到一边，例如：
【1，4，1】 【2，2，3】
这样分别对两个子数组求异或，结果：
1 ^ 4 ^ 1 = 4
2 ^ 2 ^ 3 = 3
刚好是想要的结果～～！！！！！

问题来了，如何把一个数组分成两个子数组，并且满足如下两个要求：
1.有相同的数字的两个数字必须在同一个子数组
2.没有相同数字的数字在不同的子数组

看一下整个数组的异或值：7
7 的二进制： 111
4 的二进制： 100
3 的二进制： 011

可以发现，7的第一位等于1的是最后一位，4的最后一位是0，3的最后一位是1～～
可以多印证几个异或值，明显可以得出结论异或值的最后一个=1的位可以区别这两个异或值～～
jiangjiang～～既然如此，我们可以根据异或值的最后一个=1的数字，来将数组分成两部分～
例如：
【1，2，2，4，3，1】，这个数组的异或值为7，最后一个=1的位代表的数字=1
1 的二进制 001， 1&1（1最后一位） = 1，分到左数组
【1】【】
2 的二进制 010， 1&0（2最后一位）= 0， 分到右数组
【1】 【2， 2】
4 的二进制 100， 1&0（2最后一位）= 0， 分到右数组
【1】 【2， 2， 4】
3 的二进制 011， 1&1（1最后一位） = 1，分到左数组
【1， 3，1】 【2， 2， 4】

分完了数组，在分别异或，两个数值就是我们需要的啦～～

def find_num_appera_once_2(arr):
    if not arr:
        return None
    ret = functools.reduce(lambda x,y: x^y, arr)
    div = 1
    while div & ret == 0:
        div <<= 1
    a,b = 0, 0
    for num in arr:
        if num & div == 0:
            a ^= num
        else:
            b ^= num
    return [a,b]

最后

以上就是外向猎豹为你收集整理的剑指offer实践 ——56.1.数组中只出现一次的两个数字（python版)题目一、哈希表+队列二、异或的全部内容，希望文章能够帮你解决剑指offer实践 ——56.1.数组中只出现一次的两个数字（python版)题目一、哈希表+队列二、异或所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。