今天和大家分享一下摩尔投票法(Boyer–Moore majority vote algorithm)
这里分享的是最基本的摩尔投票问题：找出一组数字序列中出现次数大于总数1/2的数字
想象一下，现在有三种颜色的一堆小球，其中有一种颜色的小球的个数超过所有小球个数的一半，现在想要知道数量最多的小球是什么颜色
1.我们先在手里拿一个小球base；2.游戏开始之后，每次从这堆小球中拿出一个小球，如果拿出的小球的颜色和base相同，那么base的个数加1；否则的话，两个小球都将“消失”；2.1 如果是base加1的这种情况，我们继续从这堆小球中拿出小球来和base做比较；2.2 如果是两个小球都消失的情况，我们需要回到步骤1；3.当最后只剩下一个小球的时候，这个颜色的小球就是符合要求的；
视频演示：
LeetCode-面试题 17.10
题目描述：
数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。
示例 1：
输入：[1,2,5,9,5,9,5,5,5]
输出：5
示例 2：
输入：[3,2]
输出：-1
示例 3：
输入：[2,2,1,1,1,2,2]
输出：2
说明：
你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？
如果之前没有接触过摩尔投票法，你会怎么做呢？我第一次遇见这道题，上去就是一趟遍历，将数组每个元素存储下来，最后保存下来的元素的个数超过数组长度一半的就是最终需要的结果；时间复杂度是O(N)，因为在存储的过程中我们使用到了集合来保存数组元素和元素出现的次数，所以空间复杂度也是O(N)；
虽然达到了时间复杂度的要求，但是题目中要求将空间复杂度降为O(1)，这也就是只让使用常数空间来进行存储；
那这个时候，摩尔投票法就能发挥它的优势了！
直接上代码：
/**
* 执行用时：2 ms, 在所有 Java 提交中击败了70.33% 的用户
* 内存消耗：41.3 MB, 在所有 Java 提交中击败了97.07% 的用户
* @param nums
* @return
*/
public int majorityElement(int[] nums) {
if (nums.length < 1) return -1;
//base
int first = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (first == nums[i]) {
count++;
} else {
count--;
}
if (count == 0) {
first = nums[i];
count = 1;
}
}
//校验
count = 0;
for(int i : nums){
if (first == i) count++;
if (count > nums.length / 2) return first;
}
return -1;
}
特别说明： 为什么最后要进行校验呢？这是因为题目中并没有明确告知我们给定的目标数组中一定存在“主要元素”，我们需要对最后得出的元素进行校验，看它是否满足“主要元素”的定义；
若有收获，就点个赞吧
0 人点赞
