169. 多数元素

题目

169. 多数元素（简单）

给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：

[3,2,3]

输出：

3

示例 2：

输入：

[2,2,1,1,1,2,2]

输出：

2

提示：

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9
• 输入保证数组中一定有一个多数元素。

思路

哈希计数：用 collections.Counter 统计每个数出现的次数，取计数最大的那个即为多数元素，时间 $O(n)$、空间 $O(n)$。

进阶：Boyer-Moore 投票算法可以做到 $O(1)$ 空间——维护候选者和票数，遇到相同数票数 +1、不同数票数 −1，票数归零就换候选者，多数元素最终一定存活。

代码

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)