作者：我脱下短袖
公众号：算法无遗策
今天分享一个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语言提交的人都没几个。
然后我们再看执行内存消耗，很优秀嘛！比Java的内存消耗要少的多。
关注「五分钟学算法」，一起领悟算法的魅力，大家加油 (●’◡’●)
END
点“在看”你懂得
原文始发于微信公众号（五分钟学算法）：LeetCode 图解 | 229.求众数Ⅱ，要求线性时间复杂度？
