Python数组中出现次数超过一半的数字
两种思路。第一种思路,出现次数超过一半的数字,不管如何,必然这个数字位于数组中间的位置,因此可以采用类似于快排的划分的方法,找到位于数组中间的位置的数字,然后在顺序检索是否这个数字出现次数超过一半。第二种思路根据数组的特点,出现次数超过一半的数,他出现的次数比其他数字出现的总和还要多,因此可以最开始保存两个数值:数组中的一个数字以及它出现的次数,然后遍历,如果下一个数字等于这个数字,那么次数加一,如果不等,次数减一,当次数等于0的时候,在下一个数字的时候重新复制新的数字以及出现的次数置为1,直到进行到最后,然后再验证最后留下的数字是否出现次数超过一半,因为可能前面的次数依次抵消掉,最后一个数字就直接是保留下来的数字,但是出现次数不一定超过一半。
- '''
- 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
- 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
- '''
-
- # -*- coding:utf-8 -*-
- class Solution:
- # 基于Partition函数的O(n)算法
- def MoreThanHalfNum_Solution(self, numbers):
- length = len(numbers)
- if length == 1:
- return numbers[0]
- if self.CheckInvalidArray(numbers, length):
- return 0
-
- middle = length >> 1
- start = 0
- end = length - 1
- index = self.Partition(numbers, length, start, end)
- while index != middle:
- if index > middle:
- end = index - 1
- index = self.Partition(numbers, length, start, end)
- else:
- start = index + 1
- index = self.Partition(numbers, length, start, end)
- result = numbers[middle]
- if not self.CheckMoreThanHalf(numbers, length, result):
- result = 0
- return result
- # 划分算法
- def Partition(self, numbers, length, start, end):
- if numbers == None or length <= 0 or start < 0 or end >= length:
- return None
- if end == start:
- return end
- pivotvlue = numbers[start]
- leftmark = start + 1
- rightmark = end
-
- done = False
-
- while not done:
- while numbers[leftmark] <= pivotvlue and leftmark <= rightmark:
- leftmark += 1
- while numbers[rightmark] >= pivotvlue and rightmark >= leftmark:
- rightmark -= 1
-
- if leftmark > rightmark:
- done = True
- else:
- numbers[leftmark], numbers[rightmark] = numbers[rightmark], numbers[leftmark]
- numbers[rightmark], numbers[start] = numbers[start], numbers[rightmark]
- return rightmark
-
- # 检查输入的数组是否合法
- def CheckInvalidArray(self, numbers, length):
- InputInvalid = False
- if numbers == None or length <= 0:
- InputInvalid = True
- return InputInvalid
- # 检查查找到中位数的元素出现次数是否超过所有元素数量的一半
- def CheckMoreThanHalf(self, numbers, length, number):
- times = 0
- for i in range(length):
- if numbers[i] == number:
- times += 1
- if times*2 <= length:
- return False
- return True
- #-------------------------------以上都是基于划分的方法寻找---------------------------------#
- # 根据数组特点找出O(n)的算法
- def MoreThanHalfNum(self, numbers):
- length = len(numbers)
- if numbers == None or length <= 0:
- return 0
- result = numbers[0]
- times = 1
- for i in range(1, length):
- if times == 0:
- result = numbers[i]
- times = 1
- elif numbers[i] == result:
- times += 1
- else:
- times -= 1
- if not self.CheckMoreThanHalf(numbers, length, result):
- result = 0
- return result
-
- S = Solution()
- # print(S.MoreThanHalfNum_Solution([1, 2, 3, 2, 2, 2, 5, 4, 2]))
- # print(S.MoreThanHalfNum_Solution([1, 2, 3, 3, 3, 3, 4]))
- # print(S.MoreThanHalfNum_Solution([1, 2]))
- print(S.MoreThanHalfNum([1, 2, 3, 2, 2, 2, 5, 4, 2]))
- print(S.MoreThanHalfNum([1, 2, 3, 3, 3, 3, 4]))
- print(S.MoreThanHalfNum([1, 2]))
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。