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

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

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

今天分享一个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 == 0return 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([]int0)
    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语言提交的人都没几个。

LeetCode 图解 | 229.求众数Ⅱ,要求线性时间复杂度?
执行用时

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

LeetCode 图解 | 229.求众数Ⅱ,要求线性时间复杂度?
内存消耗

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

END



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

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

● LeetCode图解|206.反转链表

● LeetCode图解|37.解数独

LeetCode图解|191.位1的个数


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



点“在看你懂得 

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

原文始发于微信公众号(五分钟学算法):LeetCode 图解 | 229.求众数Ⅱ,要求线性时间复杂度?

我还会在以下平台发布内容

GitHub 知乎