40.数组中只出现一次的数字(python)

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路

将数组的因为就两个数只出现一次，所以，这些数字做异或之后，得到的结果是这两个数做异或的结果，比如 1 2 1 2 3 4 5 5 4 7 做完异或就是3^7 011^111=100

在最后的结果中，从右往左找出现的第一个1，发现在第三位，把100取出来，对原数组每个数进行与运算，与左边与得到的结果都是0 与右边做与运算得到的结果都是1，这样就可以找到这两个子数组了，按这两个子数组里面每个数做异或，就得到了两个数组

中出现一次的数 3 和 7 神奇

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     # 返回[a,b] 其中ab是出现一次的两个数字
 4     def FindNumsAppearOnce(self, array):
 5         # write code here
 6         if len(array)<2:
 7             return None
 8         tmpnum = None
 9         for num in array:
10             if tmpnum==None:
11                 tmpnum = num
12             else:
13                 tmpnum ^=num
14         count = 0
15         while tmpnum%2==0:
16             tmpnum = tmpnum >>1
17             count +=1
18         mask = 1 << count
19         firstNum = None
20         secondNum = None
21         for num in array:
22             if num&mask == 0:
23                 if firstNum == None:
24                     firstNum = num
25                 else:
26                     firstNum ^=num
27             else:
28                 if secondNum == None:
29                     secondNum = num
30                 else:
31                     secondNum ^= num
32         return firstNum,secondNum
33

2019-12-23 14:58:21