欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法题/数组中出现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)

算法题/数组中出现1次的两个数

相关标签: 算法