寻找只出现过一次的数字

给定一个数组，只有一个数字出现过一次，其他均出现过两次，寻找这个只出现过一次的数
说明：算法应该有线性时间复杂度，且尽可能不使用新的内存空间
思路一：比较：首先对数组进行排序，数组长度是奇数，出现过两次的数字在相邻奇数位偶数位会同时出现。

def find(L):
    L = sorted(L)
    for i in range(0, len(L), 2):
        if L[i] != L[i+1]:
            return L[i]

find([2, 2, 4, 4, 1])
# 1

思路二：做差：排列后出现两次的数会在奇数位和偶数位各出现一次，奇数和与偶数和的差即为只出现过一次的数字。

from functools import reduce


def find_diff(L):
    L = sorted(L)
    sum_odd = reduce(lambda a,b: a+b, [L[i] for i in range(1, len(L), 2)])
    sum_even = reduce(lambda a,b: a+b, [L[i] for i in range(0, len(L), 2)])
    return sum_even - sum_odd

find_diff([2, 2, 4, 4, 1])
# 1

思路三：hashset去重：利用hashset的特性，删除重复元素，最终剩余的即为只出现过一次的数字。

def find_set(L):
    seen = set()
    for item in L:
        if item not in seen:
            seen.add(item)
        else:
            seen.remove(item)
    
    return seen.pop()

find_set([2, 2, 3, 3, 1])
# 1

思路四：异或：根据异或的特点，相同的数字运算后结果为0，最终剩余的即为只出现过一次的。

def find_xor(L):
    return reduce(lambda a, b: a^b, L)

find_xor([1,2,1])
# 2

严格意义上只有思路四是正解。那如果现在有两个数字只出现过一次，请找出这两个数字。
分析：异或运算中相同的数字最终结果为0，而此时有两个不同的数字只出现过一次，则两个数字不等，最终结果肯定不为0，且这个结果是两个只出现过一次的数字的异或的结果，所以，结果的二进制形式中至少有一位是1，即两个数的二进制形式至少有一位不同。此时我们按该位将数组分成两部分，则每部分都有切仅有一个只出现过一次的数字，然后对每部分分别进行查找只出现一次的数字即可。

def find_tow_xor(L):
    res = reduce(lambda a, b: a^b, L)
    bitindex = 0
    for i in range(32):
        # 按位进行 且 运算，找到第一个是1的index
        if res>>i & 1:
            bitindex = i
            break
    
    L_0, L_1 = [], []
    for item in L:
        if item >> bitindex & 1:
            L_1.append(item)
        else:
            L_0.append(item)
    first = find_xor(L_0)
    sec = find_xor(L_1)
    return [first, sec]

find_tow_xor([1,2, 1, 2, 11, 11, 22, 33])
#[22, 33]