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

题目描述

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

思路

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

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

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

 # -*- coding:utf-8 -*-

 class Solution:

     # 返回[a,b] 其中ab是出现一次的两个数字

     def FindNumsAppearOnce(self, array):

         # write code here

         if len(array)<2:

             return None

         tmpnum = None

         for num in array:

             if tmpnum==None:

                 tmpnum = num

             else:

                 tmpnum ^=num

         count = 0

         while tmpnum%2==0:

             tmpnum = tmpnum >>1

             count +=1

         mask = 1 << count

         firstNum = None

         secondNum = None

         for num in array:

             if num&mask == 0:

                 if firstNum == None:

                     firstNum = num

                 else:

                     firstNum ^=num

             else:

                 if secondNum == None:

                     secondNum = num

                 else:

                     secondNum ^= num

         return firstNum,secondNum

2019-12-23 14:58:21

巴特西

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

题目描述

最新文章

热门文章