LeetCode 题解工作台
多数元素 II
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 示例 1： 输入： nums = [3,2,3] 输出： [3] 示例 2： 输入： nums = [1] 输出： [1] 示例 3： 输入： nums = [1,2] 输出： [1,2] 提示： 1 4 -10 9 …
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def majorityElement(self, nums: List[int]) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：nums = [3,2,3] 输出：[3]
示例 2：
输入：nums = [1] 输出：[1]
示例 3：
输入：nums = [1,2] 输出：[1,2]
提示：
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
解题思路
方法一
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
n1 = n2 = 0
m1, m2 = 0, 1
for m in nums:
if m == m1:
n1 += 1
elif m == m2:
n2 += 1
elif n1 == 0:
m1, n1 = m, 1
elif n2 == 0:
m2, n2 = m, 1
else:
n1, n2 = n1 - 1, n2 - 1
return [m for m in [m1, m2] if nums.count(m) > len(nums) // 3]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity ranges from O(n) with hash counting or Boyer-Moore to O(n log n) with sorting. Space complexity is O(n) for hash map or O(1) for the Boyer-Moore variant. Sorting uses O(1) extra if in-place, otherwise O(n). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates tracking due to n/3 frequency limit.
- question_mark
Check whether multiple majority elements are possible; signal for Boyer-Moore.
- question_mark
Sorting may simplify counts but discuss time-space trade-offs.
常见陷阱
外企场景- error
Failing to consider that at most two elements can exceed n/3 and assuming more candidates.
- error
Using hash maps without verifying counts may include false positives.
- error
Incorrect integer division when computing ⌊ n/3 ⌋ can yield off-by-one errors.
进阶变体
外企场景- arrow_right_alt
Majority Element I where n/2 threshold simplifies to single candidate selection.
- arrow_right_alt
Find elements appearing more than n/k times for arbitrary k using extended Boyer-Moore.
- arrow_right_alt
Count elements exceeding a dynamic frequency threshold instead of fixed n/3.