Python数组中只出现一次的数字
任何一个数字异或他自己都等于0,0异或任何一个数都等于那个数。数组中出了两个数字之外,其他数字都出现两次,那么我们从头到尾依次异或数组中的每个数,那么出现两次的数字都在整个过程中被抵消掉,那两个不同的数字异或的值不为0,也就是说这两个数的异或值中至少某一位为1。我们找到结果数字中最右边为1的那一位i,然后一次遍历数组中的数字,如果数字的第i位为1,则数字分到第一组,数字的第i位不为1,则数字分到第二组。这样任何两个相同的数字就分到了一组,而两个不同的数字在第i位必然一个为1一个不为1而分到不同的组,然后再对两个组依次进行异或操作,最后每一组得到的结果对应的就是两个只出现一次的数字。
- '''
- 一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
- '''
-
- # -*- coding:utf-8 -*-
- class Solution:
- # 返回[a,b] 其中ab是出现一次的两个数字
- def FindNumsAppearOnce(self, array):
- if array == None or len(array) <= 0:
- return []
- resultExclusiveOr = 0
- for i in array:
- resultExclusiveOr ^= i
-
- indexOf1 = self.FindFirstBitIs1(resultExclusiveOr)
- num1, num2 = 0
- for j in range(len(array)):
- if self.IsBit1(array[j], indexOf1):
- num1 ^= array[j]
- else:
- num2 ^= array[j]
- return [num1, num2]
-
- def FindFirstBitIs1(self, num):
- indexBit = 0
- while num & 1 == 0 and indexBit <= 32:
- indexBit += 1
- num = num >> 1
- return indexBit
-
- def IsBit1(self, num, indexBit):
- num = num >> indexBit
- return num & 1
-
- class Solution2:
- # 返回[a,b] 其中ab是出现一次的两个数字
- def FindNumsAppearOnce(self, array):
- if array == None or len(array) <= 0:
- return []
- resultExOr = self.ExOr(array)
- i = 0
- while resultExOr and i <= 32:
- i += 1
- resultExOr = resultExOr>>1
- num1, num2 = [], []
- for num in array:
- if self.bitIs1(num, i):
- num1.append(num)
- else:
- num2.append(num)
- first = self.ExOr(num1)
- second = self.ExOr(num2)
- return [first, second]
-
- def ExOr(self, aList):
- ExOrNum = 0
- for i in aList:
- ExOrNum = ExOrNum ^ i
- return ExOrNum
- def bitIs1(self, n, i):
- n = n >> (i-1)
- return n & 1
-
- aList = [2, 4, 3, 6, 3, 2, 5, 5]
- s = Solution()
- print(s.FindNumsAppearOnce(aList))
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。