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

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