题目描述
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
进阶要求：时间复杂度为O(n)，空间复杂度为O(1)。
解题思路
哈希计数
直接能想到的方法是利用HashMap为每个不同的元素进行出现次数的统计。以元素值为Key，以出现次数为Value：
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> ans = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();
int n = nums.length;
for (int num : nums) {
String key = Integer.toString(num);
if (!map.containsKey(key))
map.put(key, 1);
else
map.replace(key, map.get(key) + 1);
}
Set<String> keys = map.keySet();
for (String key : keys) {
if (map.get(key) > n / 3)
ans.add(Integer.parseInt(key));
}
return ans;
}
}
此方法时间复杂度为O(n)，满足要求，但空间复杂度为O(n)，达不到O(1)的进阶标准。由此引入摩尔投票法进行解题。
摩尔投票法
所谓摩尔投票法，就是由n个票民相互投票，来选出获得半数票以上的当选者。n个票民轮流投出选票，如果当前投票人的票与当前候选人不一致，则使所投的这一票与候选人的一票抵消。当n个票民全部投票结束，剩下的那个候选人是当选者的唯一可能（注意，唯一可能不代表一定当选，前提是当选者存在，即可能不存在有人拿到半数票！）。
我们可以很轻松地利用反证法证明上述结论。若当选者不是候选者，即当选者已经被淘汰，则他的选票不可能过半。因为一旦选票过半，该人的选票一定会在与他人的对抗中全部获胜且有剩余，这与前述假设矛盾，可以证明当选者只可能是最后的候选者或不存在。
摩尔投票法的核心在于对抗消耗法，异己相消，同类共增。最终一定能选出胜者，而我们的众数目标就只可能在胜者中或者不存在。
改进摩尔投票法
如前所述，原始的摩尔投票法可以解决选出出现超过n/2次的众数的问题，而题目中需要求出出现超过n/3次的众数，因此需要对摩尔投票法进行改进来应用于本题。
原始的摩尔投票法只设立一个候选者席位，这是因为出现次数超过n/2的众数最多只有一个。类似地，对于出现次数超过n/3的众数，其个数不会超过2个。因此我们可以设立两个候选者席位，以期选出可能的两个目标众数。
以下代码的注释中用群雄逐鹿来类比摩尔投票法，也许可以帮助读者更直观地理解这一算法：
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> ans = new ArrayList<>();
int n = nums.length;
int candidate1 = 0; // 群雄逐鹿，决出两个强国
int candidate2 = 0;
int vote1 = 0;
int vote2 = 0;
for(int num : nums){ // 遍历所有士兵
if(vote1 > 0 && candidate1 == num){
// 当前强国1已有候选者，且当前士兵属于强国1，强国1兵力+1
vote1++;
}
else if(vote2 > 0 && candidate2 == num){
// 当前强国2已有候选者，且当前士兵属于强国2，强国2兵力+1
vote2++;
}
else if(vote1 == 0){ // 当前强国1还没有候选者，当前士兵所属国家暂时占据这个位置，此时强国1剩余兵力为1
candidate1 = num;
vote1 = 1;
}
else if(vote2 == 0){ // 当前强国2还没有候选者，当前士兵所属国家暂时占据这个位置，此时强国2剩余兵力为1
candidate2 = num;
vote2 = 1;
}
else{
// 当前士兵不属于强国1和强国2，与它们的士兵厮杀，强国1和强国2兵力均减1
vote1--;
vote2--;
}
}
// 厮杀全部结束，如果强国1或强国2的兵力仍然大于0，则所有原始兵力大于n/3的国家只可能在它们之中
// 清点战场尸体和生还的士兵，确认是否有国家原始兵力大于n/3，因为有可能最后的两个候选者只是因为晚参战才留了下来
int count1 = 0;
int count2 = 0;
for(int num : nums){
if(vote1 > 0 && candidate1 == num)
count1++;
if(vote2 > 0 && candidate2 == num)
count2++;
}
if(count1 > n / 3){
ans.add(candidate1);
}
if(count2 > n / 3){
ans.add(candidate2);
}
return ans;
}
}
此算法时间复杂度也为O(n)，但部分条件下的优化处理在实践中可以使其表现略优于哈希计数法。由于只需要额外存储候选者席位和票数信息，空间复杂度只有O(1)。
