题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路
第一种思路是直接排序，然后取排序后数组中间位置的值，当然这个的前提是数组中存在超过一半的数字。
第二种思路是利用哈希，统计每个元素在数组中出现的次数，当次数超过一半时，返回结果。
代码
def MoreThanHalfNum_Solution(self, numbers):
dic = {}
judge = int(len(numbers)/2)
for num in numbers:
if not num in dic.keys():
dic[num] = 1
else:
dic[num] = dic[num]+1
if dic[num] > judge:
return num
return 0
网友评论