题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
这道题如果没有想到用异或来解决的话,可能就比较不容易做出来了。异或操作有一个好处在于,两个相同的数异或的结果是0,并且异或操作是满足交换率的,所以异或的顺序对结果不会有影响。
想到这一点的话,就可以知道,我们首先遍历一遍整个数组,得到所有数字的异或结果,这个结果相当于是两个只出现一次的数字的异或结果,并且这个结果一定不是0(因为这两个数不一样)。
假设这个异或的结果中,第k位为1,我们根据第k位是不是1为标准,把原数组分成两个子数组,一个子数组中每个数字的第k位都是1,另一个子子数组中每个数字的第k位都是0,这样,两个只出现一次的数分别被分到不同的子数组中,并且每对相同的数字都会被分配到同一个子数组中。
针对每一个子数组,再利用异或的方法,即可找到那个只出现一次的数字。
#encoding=utf8
'''
题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
要求时间复杂度是O(n),空间复杂度是O(1)。
'''
def find_two_unique_num(num_list):
result = 0
for num in num_list:
result ^= num
lowbit = find_lowest_bit(result)
result_1 = 0
result_2 = 0
for num in num_list:
if num & lowbit != 0:
result_1 ^= num
else:
result_2 ^= num
return (result_1, result_2)
def find_lowest_bit(num):
index = 0
while num & 1 == 0:
num = num >> 1
index = 1
return 1 << index
if __name__ == '__main__':
num_list_1 = [2, 2, 1, 3]
num_list_2 = [2, 4, 3, 6, 3, 2, 5, 5]
print find_two_unique_num(num_list_1)
print find_two_unique_num(num_list_2)