1. 问题背景与核心需求
在算法面试和实际编程中,统计数组元素的出现频率是一个经典问题。当我们需要找出数组中出现次数超过一半的数字时,这个问题就变得尤为有趣。这类问题不仅考察基础编程能力,更考验对时间/空间复杂度的优化意识。
这个问题的标准描述是:给定一个大小为n的数组,找出其中出现次数超过⌊n/2⌋的元素。假设数组非空,且总是存在满足条件的元素(这是重要的前提条件)。例如对于数组[1,2,3,2,2,2,5,4,2],数字2出现了5次,超过数组长度9的一半(4.5次),因此2就是我们需要找的数字。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 常见解法分析与对比
2.1 哈希表统计法
最直观的解法是使用哈希表(在Python中可以用字典实现)统计每个数字出现的次数。遍历数组时,将数字作为键,出现次数作为值存入哈希表,最后检查哪个数字的出现次数超过半数。
python复制def majorityElement(nums):
counts = {}
for num in nums:
counts[num] = counts.get(num, 0) + 1
if counts[num] > len(nums)//2:
return num
注意:虽然这种方法简单直接,但空间复杂度是O(n),因为最坏情况下需要存储所有不同的数字。当数组很大时,这可能成为性能瓶颈。
2.2 排序取中法
利用题目中"超过一半"的特性,我们可以先将数组排序,然后直接取中间位置的元素。因为出现次数超过一半的数字必然会占据数组的中间位置。
python复制def majorityElement(nums):
nums.sort()
return nums[len(nums)//2]
这种方法的时间复杂度取决于排序算法,通常为O(nlogn),空间复杂度为O(1)(如果使用原地排序)。虽然比哈希表法更节省空间,但时间复杂度略高。
3. 最优解法:摩尔投票算法
3.1 算法原理
摩尔投票算法(Boyer-Moore Voting Algorithm)是解决这类问题的最优方案,时间复杂度O(n),空间复杂度O(1)。其核心思想是"正负抵消":
- 初始化候选人为None,票数count为0
- 遍历数组:
- 如果count为0,选择当前数字作为新候选人
- 如果当前数字等于候选人,count加1
- 否则count减1
- 最后剩下的候选人就是结果
3.2 代码实现
python复制def majorityElement(nums):
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
3.3 为什么这个算法有效?
算法有效性的关键在于题目保证存在出现次数超过一半的数字。即使其他所有数字都联合起来"对抗"这个多数元素,由于它的数量占优,最终仍会胜出。例如:
数组:[2,2,1,1,1,2,2]
- 初始:candidate=None, count=0
- 处理2:candidate=2, count=1
- 处理2:candidate=2, count=2
- 处理1:candidate=2, count=1
- 处理1:candidate=2, count=0
- 处理1:candidate=1, count=1
- 处理2:candidate=1, count=0
- 处理2:candidate=2, count=1
最终返回2,确实是多数元素。
4. 边界情况与验证
4.1 输入验证
虽然题目保证存在解,但在实际工程中我们应该添加验证:
python复制def majorityElement(nums):
# 原算法找出候选者
candidate = None
count = 0
for num in nums:
if count == 0:
candid
