友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
229. 多数元素 II
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：nums = [3,2,3] 输出：[3]
示例 2：
输入：nums = [1] 输出：[1]
示例 3：
输入：nums = [1,2] 输出：[1,2]
提示：
-
1 <= nums.length <= 5 * 104 -
-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
思路分析
最简单的做是使用哈希存每个数字的出现次数，但是空间复杂度就是 \(O(n)\)。
更巧妙的解法是摩尔投票法。一个数组中，最多会出现两个出现次数大于数组长度的三分之一。所以，记录两个元素和投票次数（即出现次数），与这两个元素相同，则对应元素投票次数加一，否则两个投票次数都要减一。如果出现出现次数大于三分之一，那么最后剩余投票次数大于 0 的元素，可能就是出现次数大于三分之一的。再次遍历数组，记录出现次数，最后根据次数判断是否符合题目要求。
摩尔投票法在 169. Majority Element 中也有使用。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-07-02 19:42:032
*/
public List<Integer> majorityElement(int[] nums) {
int e1 = 1000000001, e2 = 1000000002;
int v1 = 0, v2 = 0;
for (int num : nums) {
if (num == e1) {
v1++;
} else if (num == e2) {
v2++;
} else if (v1 == 0) {
e1 = num;
v1++;
} else if (v2 == 0) {
e2 = num;
v2++;
} else {
v1--;
v2--;
}
}
int c1 = 0, c2 = 0;
for (int num : nums) {
if (v1 > 0 && num == e1) {
c1++;
}
if (v2 > 0 && num == e2) {
c2++;
}
}
List<Integer> result = new ArrayList<>();
if (c1 > nums.length / 3) {
result.add(e1);
}
if (c2 > nums.length / 3) {
result.add(e2);
}
return result;
}