数组中的多数元素（摩尔投票法）

在算法世界中，寻找数组中的多数元素是一个经典问题。多数元素指的是在数组中出现次数超过⌊n/2⌋次的元素（n为数组长度）。今天我将详细介绍一种高效解决这个问题的算法——摩尔投票法（Boyer-Moore Voting Algorithm），并通过代码实现和案例分析帮助大家理解。

问题定义

给定一个大小为n的数组，找出其中出现次数超过⌊n/2⌋次的元素。假设数组非空且一定存在多数元素。

示例：

1输入: [3, 2, 3]
2输出: 3
3
4输入: [2, 2, 1, 1, 1, 2, 2]
5输出: 2
6

暴力解法

最直观的方法是遍历数组，统计每个元素的出现次数，然后检查是否有元素出现次数超过n/2。

1def majorityElement_brute(nums):
2    for num in nums:
3        count = 0
4        for n in nums:
5            if n == num:
6                count += 1
7        if count > len(nums) // 2:
8            return num
9    return -1
10

时间复杂度：O(n²)
空间复杂度：O(1)

这种方法简单但效率低下，不适合处理大规模数据。

哈希表解法

使用哈希表存储每个元素及其出现次数，然后遍历哈希表找到多数元素。

1def majorityElement_hash(nums):
2    counts = {}
3    for num in nums:
4        counts[num] = counts.get(num, 0) + 1
5    for num, count in counts.items():
6        if count > len(nums) // 2:
7            return num
8    return -1
9

时间复杂度：O(n)
空间复杂度：O(n)

虽然时间复杂度优化了，但需要额外的空间存储哈希表。

摩尔投票法（最优解）

摩尔投票法的核心思想是“抵消”：多数元素的出现次数比其他所有元素出现次数之和还要多，因此可以通过相互抵消的方式找到多数元素。

算法步骤

初始化候选元素candidate和计数器count
遍历数组：
- 如果count为0，选择当前元素作为候选
- 如果当前元素等于候选，count加1
- 否则count减1
最终候选即为多数元素

为什么有效？

因为多数元素的出现次数比其他所有元素多，所以即使发生抵消，多数元素最终仍会保留。

代码实现

1def majorityElement(nums):
2    candidate = None
3    count = 0
4    
5    for num in nums:
6        if count == 0:
7            candidate = num
8        count += (1 if num == candidate else -1)
9    
10    return candidate
11

时间复杂度：O(n)
空间复杂度：O(1)

示例解析

以数组[2, 2, 1, 1, 1, 2, 2]为例：

元素	candidate	count
2	2	1
2	2	2
1	2	1
1	2	0
1	1	1
2	1	0
2	2	1

最终返回2，验证正确。

扩展思考

如果题目不保证多数元素存在？

可以添加一个验证步骤，再次遍历数组统计候选元素的出现次数：

1def majorityElement_verify(nums):
2    candidate = None
3    count = 0
4    
5    # 投票阶段
6    for num in nums:
7        if count == 0:
8            candidate = num
9        count += (1 if num == candidate else -1)
10    
11    # 验证阶段
12    verify_count = 0
13    for num in nums:
14        if num == candidate:
15            verify_count += 1
16    
17    return candidate if verify_count > len(nums) // 2 else None
18

寻找出现次数超过⌊n/3⌋次的元素

类似问题可以扩展到寻找出现次数超过⌊n/3⌋次的元素（最多可能有2个）。算法需要维护两个候选元素：

1def majorityElement_n3(nums):
2    if not nums:
3        return []
4    
5    # 初始化两个候选和计数器
6    candidate1, candidate2 = None, None
7    count1, count2 = 0, 0
8    
9    for num in nums:
10        if num == candidate1:
11            count1 += 1
12        elif num == candidate2:
13            count2 += 1
14        elif count1 == 0:
15            candidate1 = num
16            count1 = 1
17        elif count2 == 0:
18            candidate2 = num
19            count2 = 1
20        else:
21            count1 -= 1
22            count2 -= 1
23    
24    # 验证两个候选
25    result = []
26    for candidate in [candidate1, candidate2]:
27        if nums.count(candidate) > len(nums) // 3:
28            result.append(candidate)
29    
30    return result
31

总结

摩尔投票法是一种巧妙且高效的算法，特别适合解决多数元素问题。它通过相互抵消的思想，在O(n)时间复杂度和O(1)空间复杂度内找到多数元素。理解这种算法的关键在于：

多数元素的存在性保证了最终不会被完全抵消
计数器的增减规则实现了元素的相互抵消
算法不需要预先知道多数元素的具体值

在实际应用中，这种算法可以用于选举投票、故障检测等需要找出”主流”选择的场景。希望这篇文章能帮助你深入理解摩尔投票法！