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

数组中出现次数超过一半的数字_牛客题霸_牛客网

问题简述

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

思路：“摩尔投票”

Python

class Solution:
    def MoreThanHalfNum_Solution(self , arr: List[int]) -> int:
        
        ret = arr[0]
        cnt = 1
        
        for x in arr[1:]:
            if x == ret:
                cnt += 1
            else:
                cnt -= 1
            
            if cnt == 0:
                ret = x
                cnt = 1
        
        return ret