当前位置:网站首页>LeetCode 图解 | 229.求众数Ⅱ,要求线性时间复杂度?

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

2022-09-23 08:42:5151CTO

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

作者:我脱下短袖

公众号:算法无遗策

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

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

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

题目描述

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

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

示例 1:

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

示例 2:

      
      
输入: [ 1, 1, 1, 3, 3, 2, 2, 2]
输出: [ 1, 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;
}
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
Java执行结果
      
      
执行用时 : 2 ms , 在所有 Java 提交中击败了 99.89 % 的用户
内存消耗 : 45.5 MB , 在所有 Java 提交中击败了 5.38 % 的用户
  • 1.
  • 2.
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
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
Go语言执行结果
      
      
执行用时 : 16 ms , 在所有 Go 提交中击败了 56.67 % 的用户
内存消耗 : 5.1 MB , 在所有 Go 提交中击败了 100.00 % 的用户
  • 1.
  • 2.

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

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


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

执行用时

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


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

内存消耗

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

END



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


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



原网站

版权声明
本文为[51CTO]所创,转载请带上原文链接,感谢
https://blog.51cto.com/csnd/5705243

随机推荐