前往此题

抵消法

这题简单来讲就是按照正负抵消的方式来解。众所周知数组中的众数的数量必定大于其他数，那么一一抵消下来最后剩下来的就是最终答案了

算法思路
假设我们要求的众数为x。
通过辅助变量votes来记录正负关系，遇到数字n记作1，将n存储到变量res中代表众数x。如果再次遇到x，votes+1,遇到其他数字votes-1。

代码

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        votes = 0
        for n in nums:
            if votes == 0: res = n
            if n == res: votes += 1
            else: votes -= 1
        return res

复杂度分析

• 时间复杂度： O(N)
• 空间复杂度： O(1)

哈希法

遍历整个数组，对每个数字进行计数，找出最多的那个即可。

代码

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        hs = {}

        for n in nums:
            value = hs.get(n, 0) + 1
            hs[n] = value
            if value > len(nums) // 2:
                return n
        return None

复杂度分析

• 时间复杂度： O(N)
• 空间复杂度： O(N)