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;
        }
    }

测试通过：