算法题/数组中出现1次的两个数
程序员文章站
2022-07-15 12:06:22
...
python2.7
题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
思路:
1.一个数组中如果只有一个单独的数,其余的都成对出现,求这个数,就将数组中的每个数相异或就能得到单独的数
2.一个数组中有两个单独的数,其余的成对出现,将这些数相异或后,所得的数肯定不为0,所得的数最高位1是区分两个数的重点,将原数组分为两个部分。
例如100^001=101最高位1将两数区分,同时也将数组中其余数区分
3.求一个数的最高位1是第几位,将这个数左移几位,直到为0(最高位是第n位)
4.判断一个数的第n位是否为1,将这个数与1的右移(n-1)位相与,判断是否为0
#coding:utf-8
def find_single_number(a):
xor_result = 0
n = 0
num1 = 0
num2 = 0
for i in a:
xor_result ^= i
while xor_result:
xor_result = xor_result >> 1
n = n+1
for i in a:
if i & (1 << n-1) ==0:
num1 ^= i
else:
num2 ^= i
return [num1,num2]
result = find_single_number([1,4,4,7,8,8])
print('single nums:',result)