求解数组中只出现一次的数字 python

165 阅读 0 评论 109 点赞

我是靠谱客的博主羞涩棒棒糖，这篇文章主要介绍求解数组中只出现一次的数字 python，现在分享给大家，希望可以做个参考。

题目一：在一个数组中，只有1个数字仅出现1次，其余数字出现2次，求只出现一次的那个数字。

关键点：异或运算

相同的数字异或的结果是0：2^2=0
和0异或是本身：0^2=2

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
def one_number(alist):
    '''一个数组中只有1个数字出现1次，其余都出现偶数次'''
    a=0
    for i in alist:
        a^=i
    return a


alist=[1,2,3,1,3]
print(one_number(alist))

#执行结果：2

题目升级：在一个数组中，有且仅有2个数字出现1次，其余数字出现2次，求这两个数字。

分析：

首先把所有的数字进行异或，得到结果值（假设是a,b），得到的是a^b的结果
注：a^b!=0(重点)，我们在结果只找到第一个为1的位置，记为index,这样我们可以把原数组分为2部分，一部分的数在位置index为0，另一部分在位置index为1
这样我们的结果就分别在这两个部分了

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def two_number(alist):
    '''一个数组中有2个数字只出现1次，其余出现偶数次'''
    tmp=0
    for i in alist:
        tmp^=i

    #求index的位置
    index=0
    while tmp&1==0:
        tmp>>=1
        index+=1

    a,b=0,0
    for i in alist:
        i>>=index
        if i&1==0:
            a^=i
        else:
            b^=i
    return [a,b]


alist2=[1,2,3,4,3,4,5,5]
print(two_number(alist2))

#执行结果   [1,2]