LeetCode每日一练（主要元素）

Myth丶恋晨 2022-10-19 11:28 205阅读 0赞

题目如下：

> 数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

![在这里插入图片描述][20210710152831785.png]  
题目描述的是找出一个整数数组中的主要元素，这个主要元素的个数要超过数组长度的一半，并且要求时间复杂度为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，测试通过：  
![在这里插入图片描述][20210710154317605.png]  
虽然测试通过了，但是这道题仍然做得不太完美，两次遍历大大降低了执行效率，那么有没有办法能够提高效率呢？

我们可以采用Boyer-Moore 投票算法，其思想是从数组中删除两个不同的元素，直到投票过程无法继续，此时数组为空或者数组中剩下的元素都相等。

什么意思呢？想象一下，主要元素的个数既然超过了数组长度的一半，那么它的个数就一定大于主要元素之外的其它元素个数之和，倘若让每个非主要元素与主要元素两两相互抵消，那么最后剩下的就一定是主要元素，比如：

![在这里插入图片描述][20210710154906625.png]  
对于这样的一个数组，我们首先定义一个count变量用于记录主要元素的个数，首先假设数组的第一个元素是主要元素：  
![在这里插入图片描述][20210710155055155.png]  
接着往后遍历：  
![在这里插入图片描述][20210710155127591.png]  
此时count的值为3，继续遍历后发现数值为2，此时让count减1：  
![在这里插入图片描述][2021071015520739.png]  
遍历到第3个数值2时，count值为0，足以说明数值1一定不是主要元素，再假设下一个数值为主要元素：  
![在这里插入图片描述][20210710155315455.png]  
这样就成功求得了主要元素为2。

再来看一个更为复杂一些的例子：  
![在这里插入图片描述][20210710155536169.png]  
首先假设数值1为主要元素，发现下一个数值为2，count减1：  
![在这里插入图片描述][2021071015561595.png]  
此时证明该位置之前的元素（包括当前位置）均不是主要元素（需要注意的是仅仅是在当前位置之前可以认为不是主要元素），然后假设下一个数值5为主要元素，count加1：  
![在这里插入图片描述][20210711211456273.png]

发现下一个数值为9，count减1：  
![在这里插入图片描述][202107112115262.png]

此时假设下一个数值5为主要元素，以此类推，直到：  
![在这里插入图片描述][20210710155830269.png]  
发现下一个数值为5，count加1：  
![在这里插入图片描述][20210710155856493.png]  
下一个数值仍然为5，count加1：  
![在这里插入图片描述][20210710155914279.png]  
由此我们能够发现一个规律，当count为0时，我们就假设当前位置元素为主要元素，若是下一个元素与其相等，则count加1；若是不相等，则count减1，当count减为0时，要重新假设新的主要元素，遍历结束后，若count大于0，则假设的主要元素就是数组中的主要元素；若count不大于0，则没有主要元素。

但这并不是绝对的，比如：  
![在这里插入图片描述][20210710160647255.png]  
首先假设数值1为主要元素：  
![在这里插入图片描述][20210710160733737.png]  
发现下一个数值为2，count减1，一直减到0：  
![在这里插入图片描述][20210710160833486.png]  
此时让下一个数值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;
            }
        }

测试通过：  
![在这里插入图片描述][20210710162044434.png]

[20210710152831785.png]: /images/20221005/c3d148f45d0448c1b4d2d4a2b2b07958.png
[20210710154317605.png]: /images/20221005/52988c9388c54dd6af47e847af3e9665.png
[20210710154906625.png]: /images/20221005/86809a1f2a8b4ef185c5eb582d14dfd6.png
[20210710155055155.png]: /images/20221005/4a1e28f40f0b499aaa6ade79e537c3a6.png
[20210710155127591.png]: /images/20221005/88f1de47d5c44c09bdf38332005f0999.png
[2021071015520739.png]: /images/20221005/14523bf945404f8984b40c834d5a7b3f.png
[20210710155315455.png]: /images/20221005/94824e969dc34105a4292f427e9d340e.png
[20210710155536169.png]: /images/20221005/267d4b6de5104100a9e472d4ad78c249.png
[2021071015561595.png]: /images/20221005/457b9614b3eb461aabd0ebdcf45edaf8.png
[20210711211456273.png]: /images/20221005/43510e4bff4e41ddb8d5b09c53e8a154.png
[202107112115262.png]: /images/20221005/5f2af388f7bd4ce89e1ee661fbb21ceb.png
[20210710155830269.png]: /images/20221005/ba9e80a3e8e544098f837b68f408aa3b.png
[20210710155856493.png]: /images/20221005/5a42235af98c4b9296da37a4f5d6afce.png
[20210710155914279.png]: /images/20221005/381b4a6d0290432e95487b82e4f12a30.png
[20210710160647255.png]: /images/20221005/b38d7a6221a9451e9e37e05e905816fd.png
[20210710160733737.png]: /images/20221005/a4437f72913f40d7b563d3235a1528cb.png
[20210710160833486.png]: /images/20221005/f78f9bc38ce040968940bc884251d7f8.png
[20210710162044434.png]: /images/20221005/22f92c60b808417187be76e74a0689a1.png