LeetCode每日一练（主要元素）
LeetCode每日一练（主要元素）
题目如下：
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
题目描述的是找出一个整数数组中的主要元素，这个主要元素的个数要超过数组长度的一半，并且要求时间复杂度为O(N)，我们首先想到的解决办法就是得到数组中每个元素的个数，再去判断是否有某个元素的个数超过了数组长度的一半，若有，则找到了主要元素；若没有，则没有主要元素，返回 -1。
代码如下：
public static int majorityElement(int[] nums) {
// 计算数组中每个元素的个数
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
// 若map中存在，则数量加1
Integer count = map.get(num);
map.put(num, ++count);
} else {
// 若map中不存在，存入map，数量为1
map.put(num, 1);
}
}
AtomicInteger mainNum = new AtomicInteger(-1);
// 遍历map集合，检查是否有元素个数超过了数组长度的一半
map.forEach((k, v) -> {
if (v > nums.length / 2) {
// 若存在这样的数，则找到主要元素
mainNum.set(k);
}
});
// 若不存在，直接返回-1
return mainNum.get();
}将代码提交到LeetCode，测试通过：
虽然测试通过了，但是这道题仍然做得不太完美，两次遍历大大降低了执行效率，那么有没有办法能够提高效率呢？
我们可以采用Boyer-Moore 投票算法，其思想是从数组中删除两个不同的元素，直到投票过程无法继续，此时数组为空或者数组中剩下的元素都相等。
什么意思呢？想象一下，主要元素的个数既然超过了数组长度的一半，那么它的个数就一定大于主要元素之外的其它元素个数之和，倘若让每个非主要元素与主要元素两两相互抵消，那么最后剩下的就一定是主要元素，比如：
对于这样的一个数组，我们首先定义一个count变量用于记录主要元素的个数，首先假设数组的第一个元素是主要元素：
接着往后遍历：
此时count的值为3，继续遍历后发现数值为2，此时让count减1：
遍历到第3个数值2时，count值为0，足以说明数值1一定不是主要元素，再假设下一个数值为主要元素：
这样就成功求得了主要元素为2。
再来看一个更为复杂一些的例子：
首先假设数值1为主要元素，发现下一个数值为2，count减1：
此时证明该位置之前的元素（包括当前位置）均不是主要元素（需要注意的是仅仅是在当前位置之前可以认为不是主要元素），然后假设下一个数值5为主要元素，count加1：
发现下一个数值为9，count减1：
此时假设下一个数值5为主要元素，以此类推，直到：
发现下一个数值为5，count加1：
下一个数值仍然为5，count加1：
由此我们能够发现一个规律，当count为0时，我们就假设当前位置元素为主要元素，若是下一个元素与其相等，则count加1；若是不相等，则count减1，当count减为0时，要重新假设新的主要元素，遍历结束后，若count大于0，则假设的主要元素就是数组中的主要元素；若count不大于0，则没有主要元素。
但这并不是绝对的，比如：
首先假设数值1为主要元素：
发现下一个数值为2，count减1，一直减到0：
此时让下一个数值3作为主要元素，但事实上这个数组中并没有主要元素。
举一个比较形象的例子，倘若多个国家发生战争，战争的方式非常简单粗暴，每个国家每次都派出一个士兵两两单挑，每次单挑只有一个结果，就是同归于尽，最后只要哪边还有人存活，那么活下来的那个国家参战人数就是最多的。但事实上，若是其它国家斗得两败俱伤，却让只派出了一个士兵的国家获胜了，我们能说这个国家派出的士兵数是最多的吗？
所以该算法对于这个需求是有漏洞的，为此，我们需要在求出主要元素之后，再进行一次校验，检查它的count是否大于了数组长度的一半，如果是，才能说明它是主要元素。
最终代码如下：
public static int majorityElement(int[] nums) {
// 定义主要元素
int mainNum = -1;
// 计数器
int count = 0;
// 遍历数组
for (int num : nums) {
// 若是count = 0，则假设当前元素为主要元素
if (count == 0) {
mainNum = num;
}
if (mainNum == num) {
// 若是当前元素等于主要元素，则count加1
count++;
} else {
// 若是不等于，则count减1
count--;
}
}
// 此时mainNum即为主要元素，对其进行再次校验
count = 0;
for (int num : nums) {
if (mainNum == num) {
count++;
}
}
if (count > nums.length / 2) {
return mainNum;
} else {
return -1;
}
}测试通过：
