摩尔投票算法介绍
摩尔投票算法（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。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
图解
