Python数组中只出现一次的数字

本文阅读 2 分钟
首页 Python笔记 正文

任何一个数字异或他自己都等于0,0异或任何一个数都等于那个数。数组中出了两个数字之外,其他数字都出现两次,那么我们从头到尾依次异或数组中的每个数,那么出现两次的数字都在整个过程中被抵消掉,那两个不同的数字异或的值不为0,也就是说这两个数的异或值中至少某一位为1。我们找到结果数字中最右边为1的那一位i,然后一次遍历数组中的数字,如果数字的第i位为1,则数字分到第一组,数字的第i位不为1,则数字分到第二组。这样任何两个相同的数字就分到了一组,而两个不同的数字在第i位必然一个为1一个不为1而分到不同的组,然后再对两个组依次进行异或操作,最后每一组得到的结果对应的就是两个只出现一次的数字。

  1. '''
  2. 一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
  3. '''
  4. # -*- coding:utf-8 -*-
  5. class Solution:
  6. # 返回[a,b] 其中ab是出现一次的两个数字
  7. def FindNumsAppearOnce(self, array):
  8. if array == None or len(array) <= 0:
  9. return []
  10. resultExclusiveOr = 0
  11. for i in array:
  12. resultExclusiveOr ^= i
  13. indexOf1 = self.FindFirstBitIs1(resultExclusiveOr)
  14. num1, num2 = 0
  15. for j in range(len(array)):
  16. if self.IsBit1(array[j], indexOf1):
  17. num1 ^= array[j]
  18. else:
  19. num2 ^= array[j]
  20. return [num1, num2]
  21. def FindFirstBitIs1(self, num):
  22. indexBit = 0
  23. while num & 1 == 0 and indexBit <= 32:
  24. indexBit += 1
  25. num = num >> 1
  26. return indexBit
  27. def IsBit1(self, num, indexBit):
  28. num = num >> indexBit
  29. return num & 1
  30. class Solution2:
  31. # 返回[a,b] 其中ab是出现一次的两个数字
  32. def FindNumsAppearOnce(self, array):
  33. if array == None or len(array) <= 0:
  34. return []
  35. resultExOr = self.ExOr(array)
  36. i = 0
  37. while resultExOr and i <= 32:
  38. i += 1
  39. resultExOr = resultExOr>>1
  40. num1, num2 = [], []
  41. for num in array:
  42. if self.bitIs1(num, i):
  43. num1.append(num)
  44. else:
  45. num2.append(num)
  46. first = self.ExOr(num1)
  47. second = self.ExOr(num2)
  48. return [first, second]
  49. def ExOr(self, aList):
  50. ExOrNum = 0
  51. for i in aList:
  52. ExOrNum = ExOrNum ^ i
  53. return ExOrNum
  54. def bitIs1(self, n, i):
  55. n = n >> (i-1)
  56. return n & 1
  57. aList = [2, 4, 3, 6, 3, 2, 5, 5]
  58. s = Solution()
  59. print(s.FindNumsAppearOnce(aList))
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python判断平衡二叉树
« 上一篇 01-21
Python和为s的两个数字
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18486 篇
  • 评论总数:
    53239 条
  • 标签总数:
    8858 个
  • 总浏览量:
    21476497 次
  • 最后更新:
    2月8日

最多点赞

随便看看

标签TAG