[Python知识库]JZ28 数组中出现次数超过一半的数字 python

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

my version

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        dic = {} # {num: count}
        count = len(numbers) // 2
        for n in numbers:
            if n in dic:
                dic[n] += 1
            else:
                dic[n] = 1
            if dic[n] > count:
                return n 

book method
类似快排的partition，由于超过半数的数字一定在拍好序的中位数上

import random
class Solution:
    def partition(self, numbers, start, end):
        index = random.randint(start, end)
        small = start-1 
        numbers[index], numbers[-1] = numbers[-1], numbers[index]
        for i in range(start, end):
            if numbers[i] < numbers[-1]:
                small += 1
                numbers[small], numbers[i] = numbers[i], numbers[small]
        small += 1
        numbers[small], numbers[-1] = numbers[-1], numbers[small]
        return small
    def MoreThanHalfNum_Solution(self, numbers):
        start = 0
        end = len(numbers)-1
        index = self.partition(numbers, start, end)
        mid = len(numbers) >> 1
        while index != mid:
            if index < mid:
                start = index + 1
                index = self.partition(numbers, start, end)
            else:
                end = index - 1
                index = self.partition(numbers, start, end)
        return numbers[index]