image.png
解法一：空间换时间：用最大值个桶，来存储出现次数：
# -*- coding:utf-8 -*-
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
length = len(numbers)
book = [0] * (max(numbers)+1)
for x in numbers:
book[x] += 1
t = max(book)
for i in range(len(book)):
if book[i] > length/2:
return i
return 0
解法二：
先排序，然后用o(n)的时间，但是排序的最少时间是nlog(n)
# -*- coding:utf-8 -*-
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
s = sorted(numbers)
i = 1
if len(numbers) == 1:
return numbers[0]
while i < len(s):
j = i
cur = 1
while j < len(numbers) and s[j] == s[j-1] :
cur += 1
j += 1
i += 1
if cur > len(s)/2:
return s[j-1]
i += 1
return 0
