1. 问题背景与核心需求
这道题目来自《剑指Offer》第28题,是面试中经常出现的经典算法问题。题目要求在一个长度为n的数组中找到出现次数超过一半的数字。这个问题看似简单,但考察了候选人对时间/空间复杂度的把控能力,以及对不同算法场景的适用性判断。
在实际开发中,类似的需求经常出现在数据分析、用户行为统计等场景。比如:
- 统计系统中高频访问的IP地址
- 分析电商平台热销商品
- 识别社交网络中的热点话题
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 常见解法分析与对比
2.1 哈希表统计法
最直观的解法是使用哈希表统计每个数字出现的次数:
python复制def majorityElement(nums):
counts = {}
for num in nums:
counts[num] = counts.get(num, 0) + 1
if counts[num] > len(nums)//2:
return num
return -1
时间复杂度:O(n)
空间复杂度:O(n)
提示:虽然这种方法简单直接,但在处理海量数据时,哈希表可能占用过多内存。
2.2 排序取中法
利用题目中"超过一半"的特性,可以先排序后直接取中间值:
python复制def majorityElement(nums):
nums.sort()
return nums[len(nums)//2]
时间复杂度:O(nlogn)
空间复杂度:O(1)或O(n)(取决于排序实现)
2.3 摩尔投票法
最优解法是摩尔投票算法(Boyer-Moore Voting Algorithm):
python复制def majorityElement(nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
时间复杂度:O(n)
空间复杂度:O(1)
3. 摩尔投票算法深度解析
3.1 算法原理
摩尔投票法的核心思想是"正负抵消"。算法维护两个变量:
- candidate - 当前候选众数
- count - 候选数的相对票数
遍历数组时:
- 遇到相同数字则count+1
- 遇到不同数字则count-1
- 当count归零时更换候选数
3.2 数学证明
假设存在众数m,其出现次数>n/2:
- 非m的数字最多有n/2-1个
- 每个非m数字最多抵消一个m
- 最终剩余的m至少有一个未被抵消
3.3 边界情况处理
实际编码时需要验证结果是否确实超过半数:
python复制def majorityElement(nums):
# 摩尔投票部分...
# 验证阶段
count = 0
for num in nums:
if num == candidate:
count += 1
return candidate if count > len(nums)//2 else -1
4. 性能对比与选型建议
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 哈希统计 | O(n) | O(n) | 数据量不大,需要精确统计 |
| 排序取中 | O(nlogn) | O(1) | 允许修改原数组 |
| 摩尔投票 | O(n) | O(1) | 大数据量,内存受限 |
选型建议:
- 面试中优先实现摩尔投票法
- 实际工程中根据数据特点选择:
- 数据可放入内存 → 哈希表
- 数据量极大 → 摩尔投票
- 允许预处理 → 排序
5. 变种问题与扩展思考
5.1 出现次数超过1/3的数字
类似思路可以扩展到找出现次数超过n/3的数字:
python复制def
