题解 | #数组中出现次数超过一半的数字#

法一：哈希方法。 类似#第一个只出现一次的字符# https://blog.nowcoder.net/n/6aa6f3ed254041a88572510af837616e

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        #统计每个字符出现的次数
        mydict={}

        for i in numbers:
            if i not in mydict:
                mydict[i]=1
            else:
                mydict[i]=mydict[i]+1
                 
        #找到出现的次数超过数组长度的一半的数字       
        for i in numbers:
            if mydict[i]>len(numbers)/2:
                return i    
        return -1

时间复杂度：O(n)

空间复杂度：O(n)

法二：先将数组排序，出现次数超过一半的数字肯定在数组中间位置。

时间复杂度：O(nlongn)

空间复杂度：O(1)

法三：Boyer-Moore 投票算法

如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。这里要满足一个条件：该众数要大于总数量的一半。

算法步骤：初始化数组中第一个元素作为候选元素candidate，并设置其出现次数为count=0。遍历数组，当遇到与candidate相同的元素，count+1；不同的元素，count-1。当count为0的时候，更新候选元素为下一个元素。遍历到数组的最后，剩下的candidate就是要求的结果。

class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        count=0
        candidate=numbers[0]
        for i in range(len(numbers)):
            if numbers[i]==candidate:
                count=count+1
            else:
                count=count-1
            
            if count==0:
                candidate=numbers[i+1]
        return candidate
    #最后count一定不会是0，一定大于等于1

时间复杂度：O(n)。只对数组进行了一次遍历。

空间复杂度：O(1)。只需要常数级别的额外空间。