[特殊字符] 数组中的多数元素 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):nlen(arr)res[]foriinrange(n):# 统计 arr[i] 的频率cnt0forjinrange(i,n):ifarr[j]arr[i]:cnt1# 检查 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]resfindMajority(arr)foreleinres:print(ele,end )输出1 2注意我们也可以通过排序然后进行一次遍历来解决这个问题时间复杂度为 O(n log n)。另一种方法是使用哈希表统计频率可以在线性时间内解决但需要 O(n) 的额外空间。下面的方法可以在线性时间和常数额外空间内解决。期望方法Boyer-Moore投票算法 - O(n) 时间 O(1) 空间思路基于这样一个观察最多只能有两个多数元素它们出现的次数超过 n/3 次。当我们遍历数组时通过跟踪两个候选元素及其各自的计数来识别潜在的多数元素。步骤初始化两个候选变量 ele1 -1 和 ele2 -1以及两个计数变量 cnt1 0 和 cnt2 0。在每次迭代中如果当前元素等于某个候选元素则更新该候选元素的计数。如果某个候选元素的计数变为零则用当前元素替换该候选元素。如果当前元素既不匹配任何候选元素且两个计数都非零则两个计数都减 1。在第二轮遍历中检查选出的候选元素是否在数组中出现超过 n/3 次。如果是则将其包含在结果数组中。为什么有效任何出现次数超过 floor(n/3) 次的元素都会比出现频率较低的元素占据优势。每当我们遇到一个不同的元素我们就减少两个候选元素的计数。这保证了数组中最多只有两个候选元素。代码实现简化版deffindMajority(arr):nlen(arr)# 初始化两个候选元素及其计数ele1,ele2-1,-1cnt1,cnt20,0foreleinarr:# 增加候选元素 1 的计数ifele1ele:cnt11# 增加候选元素 2 的计数elifele2ele:cnt21# 如果候选元素 1 的计数为零设置新候选elifcnt10:ele1ele cnt11# 如果候选元素 2 的计数为零设置新候选elifcnt20:ele2ele cnt21# 如果都不匹配两个计数都减 1else:cnt1-1cnt2-1res[]cnt1,cnt20,0# 统计候选元素出现的次数foreleinarr:ifele1ele:cnt11ifele2ele:cnt21# 如果是多数元素则添加到结果中ifcnt1n/3:res.append(ele1)ifcnt2n/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]resfindMajority(arr)foreleinres:print(ele,end )输出1 2复杂度分析方法时间复杂度空间复杂度朴素方法嵌套循环O(n²)O(1)排序方法O(n log n)O(1)哈希表方法O(n)O(n)Boyer-Moore投票算法O(n)O(1)Boyer-Moore投票算法是解决这类问题的最优方案它在线性时间内完成并且只使用常数级别的额外空间非常适合处理大规模数据。