题目 求众数Ⅱ
给定一个大小为 n 的整数数组，找出其中所有出现超过 ? n/3 ? 次的元素。
示例 1：
输入：[3,2,3]
输出：[3]
示例 2：
输入：nums = [1]
输出：[1]
示例 3：
输入：[1,1,1,3,3,2,2,2]
输出：[1,2]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element-ii
思路
首先需要弄清楚题目的关键点，那就是题目要求为超过 ? n/3 ? 次的元素。也就是说，如果出现这样的用例：
输入：[1,2,3]
输出：[]
输出应该是空集，因为题目要求是超过? n/3 ? 次的元素，等于是不可以的。
如果用哈希表解决这个问题不是什么难事儿，就是需要的空间开销真的不算小，但是这题居然可以用摩尔投票法（在求n/2次以上的众数时采用过这个算法，不过我可能没写这题解法的文章……）。
摩尔投票法
这里尽量用最简单的方式解释摩尔投票法。将题目变为找到出现超过 ? n/2 ? 次的元素，讲起来更好理解。
思路就是，将两两不相同的数字进行消除，当我们重复到最后，剩余的那个数字，自然就是答案。原理也很简单：假设下面这个情况：
输入：[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]
我们对1，2，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;
}
};
|