摩尔投票算法介绍
摩尔投票算法（Boyer-Moore Majority Vote Algorithm）是一种用于查找数组中出现次数超过一半的主要元素的高效算法。它的核心思想是通过消除不同的元素对来找到主要元素，这个算法的时间复杂度为 O(n)，其中 n 是数组的长度。下面是该算法的基本原理：
- 初始化两个变量
candidate和count，其中candidate用于保存候选主要元素，count用于记录候选主要元素出现的次数。初始时，candidate可以是任何数组中的元素，而count初始化为0。 - 遍历数组中的每个元素：
- 如果
count等于0，将当前元素设置为候选主要元素candidate，并将count设置为1。 - 如果
count不等于0，检查当前元素是否等于candidate：
- 如果相等，将
count递增1，表示找到了一个与候选主要元素相同的元素。 - 如果不相等，将
count递减1，表示找到了一个与候选主要元素不同的元素。
- 在遍历完成后，
candidate变量中存储的元素就是数组中的主要元素。
这个算法的核心思想在于消除不同元素对，最终剩下的元素就是主要元素，因为主要元素的出现次数超过一半。算法的优点是只需要进行一次遍历，具有较低的时间复杂度和空间复杂度。
摩尔投票算法适用于大多数寻找主要元素的问题，例如，查找出现次数超过一半的元素，查找众数等。它是一个高效的算法，通常用于解决此类问题。
案例
假设我们有一个数组 [2, 2, 1, 1, 1, 2, 2]，我们要找出其中出现次数超过一半的主要元素。
- 初始化
candidate为2，count为1，开始遍历数组。 - 继续遍历，遇到相同的元素
2，count增加。 - 继续遍历，遇到相同的元素
2，count再次增加 - 继续遍历，遇到不同的元素
1，count减少。 - 继续遍历，遇到相同的元素
1，count增加。 - 继续遍历，遇到相同的元素
1，count再次增加。 - 继续遍历，遇到不同的元素
2，count减少。 - 继续遍历，遇到相同的元素
2，count增加。 - 继续遍历，遇到相同的元素
2，count再次增加 - 完成遍历后，
candidate变量中的元素2就是数组中的主要元素。
这就是摩尔投票算法的工作原理，通过不断消除不同的元素对，最终找到了主要元素。在这个示例中，主要元素是 2。算法只需要进行一次遍历，具有高效的时间复杂度。
摩尔投票算法，解决的问题是如何在任意多的候选人中，选出票数超过一半的那个人。假设投票是这样的，[A, C, A, A, B]，ABC 是指三个候选人。
- 第一张票与第二张票进行对坑，如果票不同则互相抵消掉；
- 接着第三票与第四票进行对坑，如果票相同，则增加这个候选人的可抵消票数；
- 这个候选人拿着可抵消票数与第五张票对坑，如果票不同，则互相抵消掉，即候选人的可抵消票数 -1。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
图解
