229. 多数元素 II
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
1
2
输入：nums = [3,2,3]
输出：[3]
示例 2：
1
2
输入：nums = [1]
输出：[1]
示例 3：
1
2
输入：nums = [1,2]
输出：[1,2]
提示：
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
推荐阅读帖子：https://writings.sh/post/boyer%E2%80%93moore-majority-vote
本题的规则就是，准备2个候选人，只要出现其中一个，那么就相应加1；如果都不是这2个那么就这俩的票数都减1
只要有一个票数是0，就替换
另外最终的候选者并不一定是要找的众数
但是消掉的数字一定不是要找的众数
看一个例子：
假设数组是 [A, B, A, B, C, B, C, D, B], 下面模拟整个投票过程， 左边的三列分别是两个候选者和抵消者，右边是当前轮次的输入。
在这个图中，X 矩阵的个数不超过 N, 一共有三列。
而抵消的时机是一行中的三个元素互不相同，那么一个元素在 X 矩阵中的每一行中至多出现一次。 也就是说 X 矩阵中的任一个数字的出现次数都不会超过 N/3 次。
也就是说，X 矩阵排除了不可能成为目标众数的元素。剩下的两个候选元素是仅剩的可能。
显然，这个分析可以直接推广到 N/K 的情况。
需要强调的是，从分析中可以看到，摩尔投票算法仅仅排除了不可能的元素，它并没有保证剩余的元素就是目标众数。 我们还需要再实际统计验证一下。因为最终要验证的候选元素的个数是常数的 K 个，所以最终总的时间复杂度也不会超过 O(N) 。
我的解法
结合上面的思路，我写了下面的解法。
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
class Solution {
public List<Integer> majorityElement(int[] nums) {
int N = nums.length;
List<Integer> res = new ArrayList<>();
int countA = 0, countB = 0, candidateA = Integer.MIN_VALUE, candidateB = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
if (countA > 0 && nums[i] == candidateA) {
countA++;
} else if (countB > 0 && nums[i] == candidateB) {
countB++;
} else if (countA == 0) {
candidateA = nums[i];
countA = 1;
} else if (countB == 0) {
candidateB = nums[i];
countB = 1;
} else {
countB--;
countA--;
}
}
int na = 0, nb = 0;
for (int n : nums){
if (n == candidateA) na++;
if (n == candidateB) nb++;
}
if (countA > 0 && na > N / 3) res.add(candidateA);
if (countB > 0 && nb > N / 3) res.add(candidateB);
return res;
}
}
时间复杂度 O(n) 和空间复杂度 O(1) 在理论上接近最优。
注意：
在验证阶段，条件countA > 0 && na > N / 3不可简化为na > N / 3
可以看个例子验证下：
输入是：
1
[4,1,2,3,4,4,3,2,1,4]
导致最终输出是4， 4，是重复的。模拟一下就会罚下，最终，两个count都是0。
所以countA > 0 表示 candidateA 在投票结束时仍然“存活”，有可能是多数元素。
如果 countA == 0，说明 candidateA 在某个时间点被完全抵消，后续可能被其他元素替换，失去候选资格。
