每日一解 摩尔投票法原来这么厉害 求众数Ⅱ
题目 求众数Ⅱ
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：[3,2,3]
输出：[3]示例 2：
输入：nums = [1]
输出：[1]示例 3：
输入：[1,1,1,3,3,2,2,2]
输出：[1,2]来自 LeetCode 平台的问题
连接到 LeetCode 平台的路径为 https://leetcode-cn.com/problems/majority-element-ii
思路
首先需要明确题目的核心要素, 即寻找出现次数超过⌊n/3⌋次的元素. 也就是说, 如果存在这样的场景: 比如说, 在一组数据中某个特定值出现了超过⌊n/3⌋次, 那么我们就需要设计一个算法来解决这个问题.
输入：[1,2,3]
输出：[]由于题目要求选出出现次数超过⌊n/3⌋的元素，在这种情况下无法找到符合条件的结果。使用哈希表来解决这个问题并不是一件困难的事情。然而空间复杂度相对较高。不过有趣的是这类问题也可以通过摩尔投票法来解决（例如之前处理过类似的问题）。不过可能没有详细记录相关的文章内容。
摩尔投票法
采用最简明的语言阐述摩尔投票法的基本原理，并将其问题转化为寻找出现次数超过⌊n/2⌋的那个元素。具体思路是通过配对相同数字进行抵消，在反复操作后最后剩下的那个数字自然就是我们要找的答案。举个例子来说：假设我们有一个数组[1, 2, 1, 3, 1]...
输入：[1,2,3,3,3]
输出：[3]我们将1和3消除，在接下来的操作中再将2和3消除。这样最终剩下的元素就是众数3。
输入：[1,2,3,3]
输出：[]我们将1和3消除，再将2和3消除，都消除了，答案为空。
注意：还有一个特殊情况是当元素总数为奇数时最后消除后必然会剩下一个数字此时我们需要回去检查这个数字究竟是众数还是恰好被排除在外。
本题的摩尔投票法
对于本题而言，在⌊n/3⌋次以上的元素是必要的。参照处理⌊n/2⌋次的做法，则可以考虑去除三个不同的数字的情况。
输入：[1,2,3,3,3]
输出：[3]我们通过消除这三个不同的数字来处理数据集，并最终得出的结果为3即为所求的答案。同样地，在寻找超过n/k的多数元素时也可以采用类似的方法。
代码解答
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> answer;
if (nums.size() == 0) {
return answer;
}
if (nums.size() == 1) {
answer.push_back(nums[0]);
return answer;
}
int num1 = nums[0];
int count_num1 = 0;
int num2 = nums[1];
int count_num2 = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == num1) {
count_num1++;
}
else if (nums[i] == num2) {
count_num2++;
}
else if (count_num1 == 0) {
num1 = nums[i];
count_num1++;
}
else if (count_num2 == 0) {
num2 = nums[i];
count_num2++;
}
else {
count_num1--;
count_num2--;
}
}
count_num1 = 0;
count_num2 = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == num1) {
count_num1++;
}
else if (nums[i] == num2) {
count_num2++;
}
}
if (count_num1 > nums.size() / 3) {
answer.push_back(num1);
}
if (count_num2 > nums.size() / 3) {
answer.push_back(num2);
}
return answer;
}
};