摩尔投票算法：高效解决数组多数元素问题

1. 问题描述与理解

题目"数组中出现次数超过一半的数字"是一个经典的算法问题，通常出现在技术面试中。给定一个数组，我们需要找出其中出现次数超过数组长度一半的数字。如果不存在这样的数字，则返回特定值（通常为None或-1）。

这个问题看似简单，但考察了多个核心能力：

• 对数组操作的基本功
• 时间/空间复杂度的优化意识
• 边界条件的处理能力
• 多种解法的比较与选择

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 None

时间复杂度：O(n)，需要遍历整个数组
空间复杂度：O(n)，最坏情况下需要存储所有不同数字

提示：这种方法虽然简单，但在面试中往往不是最优解，面试官通常会期待更高效的解法。

2.2 排序法

另一种思路是先排序数组，然后检查中间元素：

python复制def majorityElement(nums):
    nums.sort()
    candidate = nums[len(nums)//2]
    if nums.count(candidate) > len(nums)//2:
        return candidate
    return None

时间复杂度：O(nlogn)，主要由排序决定
空间复杂度：O(1)或O(n)，取决于排序实现

3. 最优解法：摩尔投票算法

3.1 算法原理

摩尔投票算法(Boyer-Moore Voting Algorithm)可以在O(n)时间和O(1)空间内解决这个问题。其核心思想是"抵消"：

1. 维护一个候选数字和计数器
2. 遍历数组，当计数器为0时选择当前数字作为候选
3. 遇到相同数字计数器+1，不同数字计数器-1
4. 最后