Boyer-Moore 投票算法
该算法的原始研究发表在 https://www.cs.utexas.edu/~moore/best-ideas/mjrty/
该方法基本上非常简单，它依赖于这样一个事实，即如果一个元素出现超过 1/2 次，那么它在体积方面的贡献最大。
所以我们取一个元素，如果下一个元素与取的元素相同，我们将增加一个计数器，否则我们将减少计数器。如果我们按照这个逻辑，我们将在最后得到对数组体积贡献最大的元素。
注意：我们对找到重复出现多少次的频率不感兴趣，我们只需要找到在数组体积中贡献最高的元素。
让我们通过示例来了解这种方法
我们有元素，
[1 1 1 3 3 2 2 3 3 3 2 3 3]
现在，我们将候选元素作为第一个元素，并用计数 1 表示它。
现在，我们增加指针，因为下一个元素与候选元素相同，我们将增加计数。
现在，如您所见，下一个元素不是 1，因此我们减少计数并移动指针，直到计数器不为 0
因此，经过 3 次迭代后，我们的计数变为 0。现在，当计数变为 0 时，这就是我们需要更改候选元素的标志。因此，我们将候选元素从 1 更改为 2。然后重新开始计数
现在，再次因为我们得到的元素与候选元素不同，我们将减少计数并在计数变为 0 时重新实例化
现在，在几次迭代后重复相同的过程，我们得到 2。所以我们再次将计数从 2 减少到 1，但此后我们又得到 3，所以再次从 1 变为 2，最后以 3 结束。
现在，我们丢弃无用的计数，候选元素是数组中出现次数超过 1/2 的元素。
这个逻辑的整个代码如下：
类解决方案（对象）： def 多数元素（自我，数字）： """ :type nums: 列表[int] :rtype: 整数 """ 候选人 = 数字 [0] 计数 = 1 对于范围内的 i (1, len(nums))： 如果 nums[i] == 候选人： 计数 += 1 elif 计数 == 0： 候选人 = nums[i] 别的： 计数 -= 1 返回（候选人）
感谢您阅读我的文章！！！接近我 https://linktr.ee/prituldave
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明
本文链接：https://www.qanswer.top/25820/58401023
