【剑指offer】数组中只出现一次的数字 -- Python 实现

89 阅读 0 评论 59 点赞

我是靠谱客的博主大气皮皮虾，这篇文章主要介绍【剑指offer】数组中只出现一次的数字 -- Python 实现，现在分享给大家，希望可以做个参考。

【题目描述】
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
【解题思路】
假设一个整型数组中除了一个数字之外，其他的数字都出现了两次，那么可以直接通过将所有元素进行异或操作找出这个只出现一次的数字，因为相同的数字异或等于0，一个数字和0异或的结果就是这个数字，所以最终将所有的元素进行异或操作得到的结果就是这个只出现一次的数字。
现在整型数组中除了两个数字之外，其他的数字都出现了两次，将所有的元素进行异或操作的结果是这两个只出现一次的数字的异或值，这个异或值一定至少有一位是1，因为这两个数字必定至少有一位不相同，以这个不相同的一位对整型数组进行划分可以分为两组，每一组必定有一个只出现一次的数字和若干对出现两次的数字，每一组用一开始得到的异或值和这一组中所有元素进行异或操作就可以得到那个只出现了一次的数字。用python实现的代码如下：

复制代码

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
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # 相同的数字异或的结果是0，最终的异或结果是res1和res2
        xor_res = 0
        for item in array:
            xor_res = xor_res ^ item
        
        # 找出res1和res2不同的那一位，因为不同的那一位的异或值是1
        index = 1
        while (index & xor_res)==0 :
            index = index << 1
        
        # 根据不一样的那一位分成两组，每一组由一个只出现一次的数字和若干对出现两次的数字组成，用异或操作就可以找出那个只出现一次的数字
        res1 = 0
        res2 = 0
        for item in array:
            if (index & item) == 0:
                res1 = res1 ^ item
            else:
                res2 = res2 ^ item
        return [res2 ,res1]