Problem: 169. 多数元素

思路

利用哈希表计数，遍历一遍数组此时时间复杂度为$O(n)$，空间复杂度为$O(n)$。

参考K神学会摩尔投票法

这个方法思想很简单，就是模拟投票，且正负票抵消。在本题中，首先假定一个多数元素，遍历元素，如果元素等于多数元素啧票数加1，否则减一。

解题方法

摩尔投票法

初始化：vetoes=0：票数， x=-1：多数元素
依次遍历元素，如果元素等于x，则票数加1，即vetoes+=1
否则，票数减1，即vetoes-=1
当票数为0时，x就是当前遍历到的元素。
返回最后一个x即可。

复杂度

时间复杂度: $O(n)$ 一次遍历

空间复杂度: $O(1)$ vetoes和x中间变量

Code

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        votes = 0 # 票数
        x = -1 # 众数，这里与数学定义不同，指的是出现次数大于n // 2的元素
        for i in nums:
            if votes == 0:
                x = i # 记votes=0的情况下的当前数字为众数
            if i == x:
                votes += 1
            else:
                votes -= 1
        
        # 若题目没有规定【给定的数组总是存在多数元素】
        # 需要判断一下x是否为众数
        cnt = 0
        for i in nums:
            if i == x:
                cnt += 1
            
        return x if cnt > len(nums) // 2 else -1