Python数组中出现次数超过一半的数字

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

两种思路。第一种思路,出现次数超过一半的数字,不管如何,必然这个数字位于数组中间的位置,因此可以采用类似于快排的划分的方法,找到位于数组中间的位置的数字,然后在顺序检索是否这个数字出现次数超过一半。第二种思路根据数组的特点,出现次数超过一半的数,他出现的次数比其他数字出现的总和还要多,因此可以最开始保存两个数值:数组中的一个数字以及它出现的次数,然后遍历,如果下一个数字等于这个数字,那么次数加一,如果不等,次数减一,当次数等于0的时候,在下一个数字的时候重新复制新的数字以及出现的次数置为1,直到进行到最后,然后再验证最后留下的数字是否出现次数超过一半,因为可能前面的次数依次抵消掉,最后一个数字就直接是保留下来的数字,但是出现次数不一定超过一半。

  1. '''
  2. 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
  3. 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
  4. '''
  5. # -*- coding:utf-8 -*-
  6. class Solution:
  7. # 基于Partition函数的O(n)算法
  8. def MoreThanHalfNum_Solution(self, numbers):
  9. length = len(numbers)
  10. if length == 1:
  11. return numbers[0]
  12. if self.CheckInvalidArray(numbers, length):
  13. return 0
  14. middle = length >> 1
  15. start = 0
  16. end = length - 1
  17. index = self.Partition(numbers, length, start, end)
  18. while index != middle:
  19. if index > middle:
  20. end = index - 1
  21. index = self.Partition(numbers, length, start, end)
  22. else:
  23. start = index + 1
  24. index = self.Partition(numbers, length, start, end)
  25. result = numbers[middle]
  26. if not self.CheckMoreThanHalf(numbers, length, result):
  27. result = 0
  28. return result
  29. # 划分算法
  30. def Partition(self, numbers, length, start, end):
  31. if numbers == None or length <= 0 or start < 0 or end >= length:
  32. return None
  33. if end == start:
  34. return end
  35. pivotvlue = numbers[start]
  36. leftmark = start + 1
  37. rightmark = end
  38. done = False
  39. while not done:
  40. while numbers[leftmark] <= pivotvlue and leftmark <= rightmark:
  41. leftmark += 1
  42. while numbers[rightmark] >= pivotvlue and rightmark >= leftmark:
  43. rightmark -= 1
  44. if leftmark > rightmark:
  45. done = True
  46. else:
  47. numbers[leftmark], numbers[rightmark] = numbers[rightmark], numbers[leftmark]
  48. numbers[rightmark], numbers[start] = numbers[start], numbers[rightmark]
  49. return rightmark
  50. # 检查输入的数组是否合法
  51. def CheckInvalidArray(self, numbers, length):
  52. InputInvalid = False
  53. if numbers == None or length <= 0:
  54. InputInvalid = True
  55. return InputInvalid
  56. # 检查查找到中位数的元素出现次数是否超过所有元素数量的一半
  57. def CheckMoreThanHalf(self, numbers, length, number):
  58. times = 0
  59. for i in range(length):
  60. if numbers[i] == number:
  61. times += 1
  62. if times*2 <= length:
  63. return False
  64. return True
  65. #-------------------------------以上都是基于划分的方法寻找---------------------------------#
  66. # 根据数组特点找出O(n)的算法
  67. def MoreThanHalfNum(self, numbers):
  68. length = len(numbers)
  69. if numbers == None or length <= 0:
  70. return 0
  71. result = numbers[0]
  72. times = 1
  73. for i in range(1, length):
  74. if times == 0:
  75. result = numbers[i]
  76. times = 1
  77. elif numbers[i] == result:
  78. times += 1
  79. else:
  80. times -= 1
  81. if not self.CheckMoreThanHalf(numbers, length, result):
  82. result = 0
  83. return result
  84. S = Solution()
  85. # print(S.MoreThanHalfNum_Solution([1, 2, 3, 2, 2, 2, 5, 4, 2]))
  86. # print(S.MoreThanHalfNum_Solution([1, 2, 3, 3, 3, 3, 4]))
  87. # print(S.MoreThanHalfNum_Solution([1, 2]))
  88. print(S.MoreThanHalfNum([1, 2, 3, 2, 2, 2, 5, 4, 2]))
  89. print(S.MoreThanHalfNum([1, 2, 3, 3, 3, 3, 4]))
  90. print(S.MoreThanHalfNum([1, 2]))
解压密码: detechn或detechn.com

免责声明

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

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

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

Python字符串的组合
« 上一篇 01-21
Python最小的k个数
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18497 篇
  • 评论总数:
    53318 条
  • 标签总数:
    8873 个
  • 总浏览量:
    22669476 次
  • 最后更新:
    3月27日

最多点赞

随便看看

标签TAG