问题描述
给定一个整数数组，要求找出所有数组中元素出现个数超过 1/3 的元素。题目链接：点我
样例输入输出
输入：[3, 2, 3]
输出：[3]
输入：[1, 2]
输出：[1, 2]
问题解法
此题跟 LeetCode-169 类似，只不过那边是找超过1/2 的数，这边是找超过 1/3 的数，所以做法类似，都是用Boyer-Moore 算法进行求解。显然，数组中元素出现个数超过 1/3 的元素，不会超过两个（只有一个或两个），所以此处在求解过程中，需要分别判断两个候选数，如果是其中一个，则对应数量加一，如果都不是，则两个候选数的数量分别减一，如果候选数数量为0，则用新的数更新候选数。这样，数组在遍历结束后会得到两个候选数，此时还需要进行额外的操作：分别判断这两个候选数是否数量超过 1/3，这是为了避免出现 [1,2,1,1,1,1,1] 这种情况，这种情况候选数有 1 和 2，但是答案显然只有 1 不包含 2，所以最后的判断可以保证得到最终正确的答案。代码如下
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
| class Solution {
public List<Integer> majorityElement(int[] nums) {
if (nums.length == 1) {
return Collections.singletonList(nums[0]);
}
int first = Integer.MIN_VALUE;
int second = Integer.MIN_VALUE;
int firstCount = 0;
int secondCount = 0;
for (int num : nums) {
if (num == first) {
firstCount++;
continue;
}
if (num == second) {
secondCount++;
continue;
}
if (firstCount == 0) {
first = num;
firstCount++;
continue;
}
if (secondCount == 0) {
second = num;
secondCount++;
continue;
}
firstCount--;
secondCount--;
}
firstCount = 0;
secondCount = 0;
for (int num : nums) {
if (num == first) {
firstCount++;
} else if (num == second) {
secondCount++;
}
}
List<Integer> result = new ArrayList<>();
if (firstCount > nums.length / 3) {
result.add(first);
}
if (secondCount > nums.length / 3) {
result.add(second);
}
return result;
}
}
|