1. 引言

地铁上闲来无事，刷到一道算法题：

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

看题目描述很简单，那么，如何解决呢？

2. 思路1 — 双重循环查找

最简单的方案是两层循环比较。
实现非常简单：

def get_two_diff(arr):
    result = []    for i in range(len(arr)):        for j in range(len(arr)):            if arr[i] == arr[j] and i != j:                break
        else:
            result.append(arr[i])    return result

这样做的时间复杂度是 O(n^2)，空间复杂度是 O(1)
这个时间复杂度显然太高了。

3. 思路2 — 排序后遍历

通过排序，我们只要找到下一个及上一个数与当前数均不同的数即是我们要找的数。
这个算法的时间、空间复杂度主要取决于排序算法的时间、空间复杂度。
通过快速排序，我们可以实现空间复杂度 O(1)，时间复杂度 O(nlogn) 的排序。
通过基数排序，我们可以实现空间复杂度 O(n)，时间复杂度 O(n) 的排序。

下面的代码是基于基数排序的算法：

def get_two_diff(arr):
    for i in range(len(str(max(arr)))):
        bucket_list = [[] for _ in range(10)]        for a in arr:
            bucket_list[int(a / (10 ** i)) % 10].append(a)
        arr = [y for x in bucket_list for y in x]    return [arr[i] for i in range(len(arr)) if (0 < i < len(arr) - 1 and arr[i - 1] != arr[i] != arr[i + 1])            or (i == 0 and arr[i] != arr[i + 1] or i == len(arr) - 1 and arr[i] != arr[i - 1])]

4. 思路3 — 空间换时间，使用 hashmap

依赖哈希表数据查找的时间复杂度为 O(1) 的特性，使用 hash 表可以让我们通过分别遍历一次数组和哈希表完成算法的求解，从而通过增长为 O(n) 的空间复杂度，将算法的时间复杂度降为 O(n)

def get_two_diff(arr):
    numdict = {}    for a in arr:
        numdict[a] = 1 if numdict.get(a) is None else 2
    return [a for a in numdict if numdict[a] == 1]

5. 思路4 — 按位异或

如果题目变成一个数组里除了一个数字之外，其他数字都出现两次，找到这一个数字，我们很容易就可以实现了。
因为两个相同数字异或等于 0，一个数和 0 异或还是它本身，利用这一特性，将数组中所有数字异或，最终出现两次的所有数字异或结果为 0，只有出现一次的数字与 0 异或返回了它本身，于是我们找到了这个只出现了一次的数字。
但题目中出现一次的数字是两个不相同的数，所以如果我们仍然将所有数字异或，最终将会得到这两个不相同数字的异或结果，我们是否有办法在异或的结果中将两个数字还原为原来的数字或转化为寻找数组中只出现一次的一个数字呢？
办法是有的，既然两个数字是不同的，那么最终的异或结果一定不为 0，而这个结果数字中，为 1 的位表示两个出现一次的数中，这两位不同。
假设异或结果的数字中，第 n 位为 1，则说明两个只出现一次的数字中，一个第 n 位为 1，一个第 n 位为 0，我们可以将原数组划分为两个数组，分别是所有第 n 位为 0 的数组成的数组和所有第 n 位为 1 的数组成的数组，这样既可以保证所有相同的数都被放入同一个数组，也可以保证两个只出现了一次的数分别被放入两个不同的数组，于是，最终我们将问题转化为找到分别在两个数组找到每个数组中只出现一次的一个数字。

def get_two_diff(arr):
    num = 0
    for a in arr:
        num ^= a
    first_set_index = get_first_set_bit(num)
    base = 1
    for i in range(1, first_set_index):
        base *= 2
    num0 = num1 = 0
    for a in arr:        if a & base == 0:
            num0 ^= a        else:
            num1 ^= a    return num0, num1def get_first_set_bit(num, bit=1):
    if num & 1 == 1:        return bit    return get_first_set_bit(num / 2, bit + 1)

于是我们实现了时间复杂度 O(n)，空间复杂度 O(1) 的算法实现。

6. 微信公众号

欢迎关注微信公众号，以技术为主，涉及历史、人文等多领域的学习与感悟，每周三到七篇推文，全部原创，只有干货没有鸡汤。

阅读原文