题解方法
摩尔投票法
- 抵消阶段：两个不同投票进行对坑，并且同时抵消掉各一张票，如果两个投票相同，则累加可抵消的次数
- 计数阶段：在抵消阶段最后得到的抵消计数只要不为 0，那这个候选人是有可能超过一半的票数的，为了验证，则需要遍历一次，统计票数，才可确定。
核心代码
抵消阶段
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
| int candidate1 = Integer.MAX_VALUE;
int candidate2 = Integer.MAX_VALUE;
int vote1 = 0;
int vote2 = 0;
for (int num: nums) {
if (candidate1 == num) {
vote1++;
}
else if (candidate2 == num) {
vote2++;
}
else if (vote1 == 0) {
candidate1 = num;
vote1++;
}
else if (vote2 == 0) {
candidate2 = num;
vote2++;
}
else {
vote1--;
vote2--;
}
}
|
计数阶段
1
2
3
4
5
6
7
8
9
10
| vote1 = 0;
vote2 = 0;
for (int num : nums) {
if (candidate1 == num) {
vote1++;
}
if (candidate2 == num) {
vote2++;
}
}
|
题目来源
229. 求众数 II - 力扣（LeetCode） (leetcode-cn.com)