[特殊字符] 数组中的多数元素 II：Boyer-Moore投票算法详解

问题描述

给定一个包含 n 个整数的数组 arr[]，找出所有出现次数超过 floor(n/3) 次的数组元素。

注意：返回的多数元素数组应该是排序的。

示例：

• 输入：arr[] = [2, 2, 3, 1, 3, 2, 1, 1]
  输出：[1, 2]
  解释：1 和 2 的频率都是 3，大于 floor(8/3) = 2。

• 输入：arr[] = [-5, 3, -5]
  输出：[-5]
  解释：-5 的频率是 2，大于 floor(3/3) = 1。

• 输入：arr[] = [3, 2, 2, 4, 1, 4]
  输出：[ ]
  解释：没有多数元素。

目录

• 朴素方法：使用嵌套循环 - O(n²) 时间 & O(1) 空间
• 期望方法：Boyer-Moore投票算法 - O(n) 时间 & O(1) 空间

说实话，啃这种算法题，光看文字推导确实容易绕晕。最近发现一个叫图码的网站，把Boyer-Moore这种算法的执行过程做成了交互式动画，每一步怎么投票、怎么抵消，拖一下进度条就全明白了。它不仅有60多种算法的可视化演示，还支持你把自定义的测试数据或者自己写的C++/Python代码直接丢进去，自动生成动画解析。对于准备408考研和数据结构期末考试的同学，这简直是复习利器。强烈建议去体验一下，比干看代码效率高太多了。

图码-数据结构与算法交互式可视化平台
访问网站：https://totuma.cn

朴素方法：使用嵌套循环 - O(n²) 时间 & O(1) 空间

思路：

遍历所有元素，统计每个元素在数组中的频率。如果某个元素的频率大于 floor(n/3)，则将其添加到结果中。为了避免在结果中添加重复元素，可以检查该元素是否已经存在于结果中。如果已经找到了两个多数元素，就可以停止搜索。

代码实现（简化版）：

deffindMajority(arr):n=len(arr)res=[]foriinrange(n):# 统计 arr[i] 的频率cnt=0forjinrange(i,n):ifarr[j]==arr[i]:cnt+=1# 检查 arr[i] 是否是多数元素ifcnt>(n//3):# 如果结果中还没有该元素，则添加iflen(res)==0orarr[i]!=res[0]:res.append(arr[i])# 如果已经找到两个多数元素，停止搜索iflen(res)==2:ifres[0]>res[1]:res[0],res[1]=res[1],res[0]breakreturnresif__name__=="__main__":arr=[2,2,3,1,3,2,1,1]res=findMajority(arr)foreleinres:print(ele,end=" ")

输出：

1 2

注意：我们也可以通过排序然后进行一次遍历来解决这个问题，时间复杂度为 O(n log n)。另一种方法是使用哈希表统计频率，可以在线性时间内解决，但需要 O(n) 的额外空间。下面的方法可以在线性时间和常数额外空间内解决。

期望方法：Boyer-Moore投票算法 - O(n) 时间 & O(1) 空间

思路：

基于这样一个观察：最多只能有两个多数元素，它们出现的次数超过 n/3 次。当我们遍历数组时，通过跟踪两个候选元素及其各自的计数来识别潜在的多数元素。

步骤：

1. 初始化两个候选变量 ele1 = -1 和 ele2 = -1，以及两个计数变量 cnt1 = 0 和 cnt2 = 0。
2. 在每次迭代中：
   • 如果当前元素等于某个候选元素，则更新该候选元素的计数。
   • 如果某个候选元素的计数变为零，则用当前元素替换该候选元素。
   • 如果当前元素既不匹配任何候选元素，且两个计数都非零，则两个计数都减 1。
3. 在第二轮遍历中，检查选出的候选元素是否在数组中出现超过 n/3 次。如果是，则将其包含在结果数组中。

为什么有效？

任何出现次数超过 floor(n/3) 次的元素，都会比出现频率较低的元素占据优势。每当我们遇到一个不同的元素，我们就减少两个候选元素的计数。这保证了数组中最多只有两个候选元素。

代码实现（简化版）：

deffindMajority(arr):n=len(arr)# 初始化两个候选元素及其计数ele1,ele2=-1,-1cnt1,cnt2=0,0foreleinarr:# 增加候选元素 1 的计数ifele1==ele:cnt1+=1# 增加候选元素 2 的计数elifele2==ele:cnt2+=1# 如果候选元素 1 的计数为零，设置新候选elifcnt1==0:ele1=ele cnt1+=1# 如果候选元素 2 的计数为零，设置新候选elifcnt2==0:ele2=ele cnt2+=1# 如果都不匹配，两个计数都减 1else:cnt1-=1cnt2-=1res=[]cnt1,cnt2=0,0# 统计候选元素出现的次数foreleinarr:ifele1==ele:cnt1+=1ifele2==ele:cnt2+=1# 如果是多数元素，则添加到结果中ifcnt1>n/3:res.append(ele1)ifcnt2>n/3andele1!=ele2:res.append(ele2)iflen(res)==2andres[0]>res[1]:res[0],res[1]=res[1],res[0]returnresif__name__=="__main__":arr=[2,2,3,1,3,2,1,1]res=findMajority(arr)foreleinres:print(ele,end=" ")

输出：

1 2

复杂度分析

Boyer-Moore投票算法是解决这类问题的最优方案，它在线性时间内完成，并且只使用常数级别的额外空间，非常适合处理大规模数据。