LeetCode 图解 | 229.求众数Ⅱ，要求线性时间复杂度？

爱被打了一巴掌 2023-07-11 05:38 13阅读 0赞

![format_png][]

## 作者：我脱下短袖  公众号：算法无遗策 ##

今天分享一个LeetCode题，题号是229，标题是求众数Ⅱ，题目标签是数组，题目难度是中等。

这道题用map方法去做很简单，但是题目描述要求要达到线性的时间复杂度，还有常量级的空间复杂度。

这个就变得有点难了，不过有更好的算法可以达到题目的要求——摩尔投票法，具体怎么做，让我们一起来先看看题目描述吧。

### 题目描述 ###

给定一个大小为 n 的数组，找出其中所有出现超过 `⌊ n/3 ⌋` 次的元素。

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1:

输入: [3,2,3]
    输出: [3]

示例 2:

输入: [1,1,1,3,3,2,2,2]
    输出: [1,2]

### 解题 ###

我们看完题目描述之后，如果不知道摩尔投票法的算法原理，是很难想出来如何达到题目要求的。

所以，俺就先介绍摩尔投票法的原理，再配上动画。学完之后再做这道题，就会变得非常简单，编程起来速度也杠杠的。

**摩尔投票法**，解决的问题是如何在任意多的候选人中，选出票数超过一半的那个人。注意，是超出一半票数的那个人。

假设投票是这样的，\[A, C, A, A, B\]，ABC是指三个候选人。

第一张票与第二张票进行对坑，如果票不同则互相抵消掉；

接着第三票与第四票进行对抗，如果票相同，则增加这个候选人的可抵消票数；

这个候选人拿着可抵消票数与第五张票对抗，如果票不同，则互相抵消掉，即候选人的可抵消票数-1。

看下面动画，就可以理解最直观最清晰的答案了。

##### 动画：摩尔投票法抵消阶段 #####

视频大小：1.53M，比Gif格式要小，可放心观看

看完上面的动画之后，相信已经理解摩尔投票法是如何选取一个最有希望的候选人的。

但这不意味着这个候选人的票数一定能超过一半，例如 \[A, B, C\]的抵消阶段，最后得到的结果是 \[C,1\]，C候选人的票数也未能超过一半的票数。

但是俺在这里发现了一个优化，如果最后得到的可抵消票数是0的话，那他已经无缘票数能超过一半的那个人了。因为本来可能有希望的，但是被后面的一张不同的票抵消掉了。所以，在这里可以直接返回结果，无需后面的计算了。

如果最后得到的可抵消票数不为0的话，那说明他可能希望的，这是我们需要一个阶段来验证这个候选人的票数是否超过一半——**计数阶段**。

所以摩尔投票法分为两个阶段：抵消阶段和计数阶段。

抵消阶段：两个不同投票进行对坑，并且同时抵消掉各一张票，如果两个投票相同，则累加可抵消的次数；

计数阶段：在抵消阶段最后得到的可抵消票数只要不为0，那这个候选人是有可能超过一半的票数的，为了验证，则需要遍历一次，统计票数，才可确定。

摩尔投票法经历两个阶段最多消耗O(2n)的时间，也属于O(n)的线性时间复杂度，另外空间复杂度也达到常量级。

理解摩尔投票法之后，我们再回到题目描述，题目可以看作是：在任意多的候选人中，选出票数超过`⌊ 1/3 ⌋`的候选人。

我们可以这样理解，假设投票是这样的\[A, B, C, A, A, B, C\]，ABC是指三个候选人。

第1张票，第2张票和第3张票进行对坑，如果票都不同，则互相抵消掉；

第4张票，第5张票和第6张票进行对抗，如果有部分相同，则累计增加他们的可抵消票数，如\[A, 2\]和\[B, 1\]；

接着将\[A, 2\]和\[B, 1\]与第7张票进行对抗，如果票都没匹配上，则互相抵消掉，变成\[A, 1\]和\[B, 0\]。

看下面动画，就知道什么回事了。

##### 动画：摩尔投票法升级 #####

视频大小：2.63M，比Gif格式要小，可放心观看

看完动画之后，是不是理解了，是不是也清晰了。

然后按照这个思路来进行编程，后面会贴上自己写的Java和Golang代码，已加上注释。

但贴代码之前，俺要来一个归纳。

如果至多选一个代表，那他的票数至少要超过一半（`⌊ 1/2 ⌋`）的票数；

如果至多选两个代表，那他们的票数至少要超过`⌊ 1/3 ⌋`的票数；

如果至多选m个代表，那他们的票数至少要超过`⌊ 1/(m+1) ⌋`的票数。

所以以后碰到这样的问题，而且要求达到线性的时间复杂度以及常量级的空间复杂度，直接套上摩尔投票法。

接下来贴上代码：

##### Java代码 #####

class Solution {
        public List<Integer> majorityElement(int[] nums) {
            // 创建返回值
            List<Integer> res = new ArrayList<>();
            if (nums == null || nums.length == 0) return res;
            // 初始化两个候选人candidate，和他们的计票
            int cand1 = nums[0], count1 = 0;
            int cand2 = nums[0], count2 = 0;
    
            // 摩尔投票法，分为两个阶段：配对阶段和计数阶段
            // 配对阶段
            for (int num : nums) {
                // 投票
                if (cand1 == num) {
                    count1++;
                    continue;
                }
                if (cand2 == num) {
                    count2++;
                    continue;
                }
    
                // 第1个候选人配对
                if (count1 == 0) {
                    cand1 = num;
                    count1++;
                    continue;
                }
                // 第2个候选人配对
                if (count2 == 0) {
                    cand2 = num;
                    count2++;
                    continue;
                }
    
                count1--;
                count2--;
            }
    
            // 计数阶段
            // 找到了两个候选人之后，需要确定票数是否满足大于 N/3
            count1 = 0;
            count2 = 0;
            for (int num : nums) {
                if (cand1 == num) count1++;
                else if (cand2 == num) count2++;
            }
    
            if (count1 > nums.length / 3) res.add(cand1);
            if (count2 > nums.length / 3) res.add(cand2);
    
            return res;
        }
    }

##### Java执行结果 #####

执行用时 : 2 ms , 在所有 Java 提交中击败了 99.89% 的用户
    内存消耗 : 45.5 MB , 在所有 Java 提交中击败了 5.38% 的用户

##### Go语言代码 #####

import "fmt"
    
    func majorityElement(nums []int) []int {
        // 创建返回值
        var res = make([]int, 0)
        if nums == nil || len(nums) == 0 {
            return res
        }
    
        // 初始化两个候选人 candidate，以及他们的计数票
        cand1 := nums[0]
        count1 := 0
        cand2 := nums[0]
        count2 := 0
    
        //摩尔投票法
        // 配对阶段
        for _, num := range nums {
            // 投票
            if cand1 == num {
                count1++
                continue
            }
            if cand2 == num {
                count2++
                continue
            }
    
            if count1 == 0 {
                cand1 = num
                count1++
                continue
            }
            if count2 == 0 {
                cand2 = num
                count2++
                continue
            }
    
            count1--
            count2--
        }
        // 计数阶段
        count1 = 0
        count2 = 0
        for _, num := range nums {
            if cand1 == num {
                count1++
            } else if cand2 == num {
                count2++
            }
        }
    
        if count1 > len(nums)/3 {
            res = append(res, cand1)
        }
        if count2 > len(nums)/3 {
            res = append(res, cand2)
        }
        return res
    }

##### Go语言执行结果 #####

执行用时 : 16 ms , 在所有 Go 提交中击败了 56.67% 的用户
    内存消耗 : 5.1 MB , 在所有 Go 提交中击败了 100.00% 的用户

提交完之后，发现执行用时仅打败了60%不到，难道还有更多的优秀算法比这更好吗？

当我点击显示详情的时候，原来是用Go语言提交的人都没几个。

![执行用时][format_png 1] 执行用时

然后我们再看执行内存消耗，很优秀嘛！比Java的内存消耗要少的多。

![内存消耗][format_png 2] 内存消耗

关注「五分钟学算法」，一起领悟算法的魅力，大家加油 (●'◡'●)

**END**

--------------------

![format_png 3][]

● [LeetCode图解|237.删除链表中的节点][LeetCode_237.]

[● ][Link 1][LeetCode图解|206.反转链表][LeetCode_206.]

● [LeetCode图解|37.解数独][LeetCode_37.]

● [LeetCode图解|191.位1的个数][LeetCode_191._1]

![format_png 4][]

点“在看”你懂得

![format_png 5][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy95OHNTRUtOODJKbnFmMGRialJWQmljSXJ6Y2xyMjlTZ2JsQmZkMjB1YWdQeUxEZEREdjFxaWFnOEJraFp2WnZtMDlvaFZMWHA2YzFzTjZiaWF5UVA0alo5dy82NDA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbnFmMGRialJWQmljSXJ6Y2xyMjlTZ2JNRzY4Z0wxcDJZUXNYQ0xWdFJnSnhpYndxczlEb040Tlh1NVRYYWFmaWNKYVZ5NnBSWGZhQTdMZy82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbnFmMGRialJWQmljSXJ6Y2xyMjlTZ2JKcE9pY3hxd1lTZjBqWURvQXNUTXliRkZoRWhIcnZpYlkxRHZ2UGZHR2tyakJodFE5dE5uVEVwZy82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9wNldsMkxETVFsSEM2cERYeVFSYVdqbFdSNVBJaHVrSVVHVjFuZks2SDlxdEhab3huWHRWZGV6dG9GZXhrYWV2dWRtWjFNYlY5cVdOWlRYaWFvcEx5b1EvNjQw?x-oss-process=image/format,png
[LeetCode_237.]: https://blog.csdn.net/kexuanxiu1163/article/details/104528761
[Link 1]: http://mp.weixin.qq.com/s?__biz=Mzg2MzE5MjMxNQ%3D%3D&chksm=ce7ef418f9097d0e01bfe9410a9e40e9f4337c835c87e28332e6a8d8fd8b91b4794164f4c1a1&idx=1&mid=2247491980&scene=21&sn=5ef03c0108a5730fa28e492ec77e22d9#wechat_redirect
[LeetCode_206.]: https://blog.csdn.net/kexuanxiu1163/article/details/104421484
[LeetCode_37.]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e7ffccd79f6ea8036de20b93a71111351cc5eb80dc8a0ba0560d20818cd984fbfa33184e8&idx=3&mid=2247487613&scene=21&sn=4b4d61e86cdc0f500a8c6fada1514546#wechat_redirect
[LeetCode_191._1]: https://blog.csdn.net/kexuanxiu1163/article/details/104285220
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jNmdxbWhXaWFmeXI5djFSblJIZGdiRTlWTzljY2pWU0FuOGpxUXBoeUxKbDU5N1JzOUJ6RVViQlIwQUdmSmZ2a3pMOXJ1cWtUbVBBWHIyOXRISWNwRFEvNjQw?x-oss-process=image/format,png