第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0229. 求众数 II
题目地址(229. 求众数 II)
https://leetcode-cn.com/problems/majority-element-ii/
题目描述
1
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
2
3
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
4
5
6
7
示例 1：
8
9
输入：[3,2,3]
10
输出：[3]
11
示例 2：
12
13
输入：nums = [1]
14
输出：[1]
15
示例 3：
16
17
输入：[1,1,1,3,3,2,2,2]
18
输出：[1,2]
19
20
21
提示：
22
23
1 <= nums.length <= 5 * 104
24
-10^9 <= nums[i] <= 10^9
Copied!
前置知识
- 摩尔投票法
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
我们仍然可以采取同样的方法 - “摩尔投票法”， 具体的思路可以参考上面的题目。
但是这里有一个不同的是这里的众数不再是超过
1 / 2,而是超过1 / 3。题目也说明了，超过三分之一的有可能有多个实际上就是 0，1，2 三种可能。
因此我们不能只用一个 counter 来解决了。 我们的思路是同时使用两个 counter，其他思路和上一道题目一样。
最后需要注意的是这两个 counter 只是出现次数最多的两个数字, 不一定都满足条件出现次数大于 1/3，因此最后我们需要进行过滤筛选。
这里画了一个图，大家可以感受一下：
229.majority-element-ii-1
229.majority-element-ii-1
关键点解析
- 摩尔投票法
- 两个 counter
- 最后得到的只是出现次数最多的两个数字，有可能不满足出现次数大于 1/3
代码
代码支持：CPP，JS, Java, Python
CPP Code:
1
class Solution {
2
public:
3
vector<int> majorityElement(vector<int>& nums) {
4
int c1 = 0, c2 = 0, v1 = 0, v2 = 1;
5
for (int n : nums) {
6
if (v1 == n) ++c1;
7
else if (v2 == n) ++c2;
8
else if (!c1) v1 = n, ++c1;
9
else if (!c2) v2 = n, ++c2;
10
else --c1, --c2;
11
}
12
c1 = c2 = 0;
13
for (int n : nums) {
14
if (v1 == n) ++c1;
15
if (v2 == n) ++c2;
16
}
17
vector<int> v;
18
if (c1 > nums.size() / 3) v.push_back(v1);
19
if (c2 > nums.size() / 3) v.push_back(v2);
20
return v;
21
}
22
};
Copied!
JS Code：
1
/*
2
* @lc app=leetcode id=229 lang=javascript
3
*
4
* [229] Majority Element II
5
*/
6
/**
7
* @param {number[]} nums
8
* @return {number[]}
9
*/
10
var majorityElement = function (nums) {
11
const res = [];
12
const len = nums.length;
13
let n1 = null,
14
n2 = null,
15
cnt1 = 0,
16
cnt2 = 0;
17
18
for (let i = 0; i < len; i++) {
19
if (n1 === nums[i]) {
20
cnt1++;
21
} else if (n2 === nums[i]) {
22
cnt2++;
23
} else if (cnt1 === 0) {
24
n1 = nums[i];
25
cnt1++;
26
} else if (cnt2 === 0) {
27
n2 = nums[i];
28
cnt2++;
29
} else {
30
cnt1--;
31
cnt2--;
32
}
33
}
34
35
cnt1 = 0;
36
cnt2 = 0;
37
38
for (let i = 0; i < len; i++) {
39
if (n1 === nums[i]) {
40
cnt1++;
41
} else if (n2 === nums[i]) {
42
cnt2++;
43
}
44
}
45
46
if (cnt1 > (len / 3) >>> 0) {
47
res.push(n1);
48
}
49
if (cnt2 > (len / 3) >>> 0) {
50
res.push(n2);
51
}
52
53
return res;
54
};
Copied!
Java Code：
1
/*
2
* @lc app=leetcode id=229 lang=java
3
*
4
* [229] Majority Element II
5
*/
6
class Solution {
7
public List<Integer> majorityElement(int[] nums) {
8
List<Integer> res = new ArrayList<Integer>();
9
if (nums == null || nums.length == 0)
10
return res;
11
int n1 = nums[0], n2 = nums[0], cnt1 = 0, cnt2 = 0, len = nums.length;
12
for (int i = 0; i < len; i++) {
13
if (nums[i] == n1)
14
cnt1++;
15
else if (nums[i] == n2)
16
cnt2++;
17
else if (cnt1 == 0) {
18
n1 = nums[i];
19
cnt1 = 1;
20
} else if (cnt2 == 0) {
21
n2 = nums[i];
22
cnt2 = 1;
23
} else {
24
cnt1--;
25
cnt2--;
26
}
27
}
28
cnt1 = 0;
29
cnt2 = 0;
30
for (int i = 0; i < len; i++) {
31
if (nums[i] == n1)
32
cnt1++;
33
else if (nums[i] == n2)
34
cnt2++;
35
}
36
if (cnt1 > len / 3)
37
res.add(n1);
38
if (cnt2 > len / 3 && n1 != n2)
39
res.add(n2);
40
return res;
41
}
42
}
Copied!
Python Code:
1
class Solution:
2
def majorityElement(self, nums):
3
c1 = c2 = 0
4
v1 = v2 = -1
5
6
for num in nums:
7
if num == v1: c1 += 1
8
elif num == v2: c2 += 1
9
elif c1 == 0:
10
c1 = 1
11
v1 = num
12
elif c2 == 0:
13
c2 = 1
14
v2 = num
15
else:
16
c1 -= 1
17
c2 -= 1
18
# check
19
c1 = c2 = 0
20
for num in nums:
21
if v1 == num: c1 += 1
22
if v2 == num: c2 += 1
23
ans = []
24
if c1 > len(nums)//3: ans.append(v1)
25
if c2 > len(nums)//3: ans.append(v2)
26
return list(set(ans))
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$
扩展
如果题目中 3 变成了 k，怎么解决？
大家可以自己思考一下，我这里给一个参考链接：https://leetcode.com/problems/majority-element-ii/discuss/63500/JAVA-Easy-Version-To-Understand!!!!!!!!!!!!/64925
这个实现说实话不是很好，大家可以优化一下。
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
最近更新 6mo ago