摩尔投票的原理详解

摩尔投票算法介绍

摩尔投票算法（Boyer-Moore Majority Vote Algorithm）是一种用于查找数组中出现次数超过一半的主要元素的高效算法。它的核心思想是通过消除不同的元素对来找到主要元素，这个算法的时间复杂度为 O(n)，其中 n 是数组的长度。下面是该算法的基本原理：

1. 初始化两个变量 candidate 和 count，其中 candidate 用于保存候选主要元素，count 用于记录候选主要元素出现的次数。初始时，candidate 可以是任何数组中的元素，而 count 初始化为0。
2. 遍历数组中的每个元素：
   • 如果 count 等于0，将当前元素设置为候选主要元素 candidate，并将 count 设置为1。
   • 如果 count 不等于0，检查当前元素是否等于 candidate：
     • 如果相等，将 count 递增1，表示找到了一个与候选主要元素相同的元素。
     • 如果不相等，将 count 递减1，表示找到了一个与候选主要元素不同的元素。
3. 在遍历完成后，candidate 变量中存储的元素就是数组中的主要元素。

这个算法的核心思想在于消除不同元素对，最终剩下的元素就是主要元素，因为主要元素的出现次数超过一半。算法的优点是只需要进行一次遍历，具有较低的时间复杂度和空间复杂度。

摩尔投票算法适用于大多数寻找主要元素的问题，例如，查找出现次数超过一半的元素，查找众数等。它是一个高效的算法，通常用于解决此类问题。

案例

假设我们有一个数组 [2, 2, 1, 1, 1, 2, 2]，我们要找出其中出现次数超过一半的主要元素。

1. 初始化 candidate 为 2，count 为 1，开始遍历数组。
2. 继续遍历，遇到相同的元素 2，count 增加。
3. 继续遍历，遇到相同的元素 2，count 再次增加
4. 继续遍历，遇到不同的元素 1，count 减少。
5. 继续遍历，遇到相同的元素 1，count 增加。
6. 继续遍历，遇到相同的元素 1，count 再次增加。
7. 继续遍历，遇到不同的元素 2，count 减少。
8. 继续遍历，遇到相同的元素 2，count 增加。
9. 继续遍历，遇到相同的元素 2，count 再次增加
10. 完成遍历后，candidate 变量中的元素 2 就是数组中的主要元素。

这就是摩尔投票算法的工作原理，通过不断消除不同的元素对，最终找到了主要元素。在这个示例中，主要元素是 2。算法只需要进行一次遍历，具有高效的时间复杂度。

摩尔投票算法，解决的问题是如何在任意多的候选人中，选出票数超过一半的那个人。假设投票是这样的，[A, C, A, A, B]，ABC 是指三个候选人。

1. 第一张票与第二张票进行对坑，如果票不同则互相抵消掉；
2. 接着第三票与第四票进行对坑，如果票相同，则增加这个候选人的可抵消票数；
3. 这个候选人拿着可抵消票数与第五张票对坑，如果票不同，则互相抵消掉，即候选人的可抵消票数 -1。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

图解

jyd - 力扣（LeetCode）图片作者