LeetCode 229. 求众数 II
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
示例 1：
输入：[3,2,3]
输出：[3]
示例 2：
输入：nums = [1]
输出：[1]
示例 3：
输入：[1,1,1,3,3,2,2,2]
输出：[1,2]
提示：
- 1 <= nums.length <= 5 * 10^4
- -10^9 <= nums[i] <= 10^9
解题思路
这道题与那道【主元素】的题目非常相似，主元素指的是出现次数超过一半，这道题是要超过 1/3。
回顾之前主元素的做法，基本思路是说，先找出候选主元素，然后检验其是否符合要求。如何筛选主元素呢？从数组中删除一些元素，以减少候选数量即可。具体来讲，是每次从数组中删除两个不同元素，如果存在主元素，那么一定会被剩下。
这里的做法也类似，也是找候选众数，然后每次找到三个不同的数，就一起删除；如果存在众数，那么一定会被剩下，最后检验即可。
推广一下这个问题，如何从n个元素中找出出现次数超过 ⌊ n/m ⌋ 的元素呢？
操作仍然是每次从数组中挑选m个不同元素进行删除操作，如果有某个元素出现次数超过 ⌊ n/m ⌋ 次，那么采取一次删除m个不同元素的操作之后，最后一定能剩下。实际上这种方法有一个专门的名称，【摩尔投票法】。
参考代码
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
constexpr static int INVALID_VALUE = INT32_MIN;
int m1 = INVALID_VALUE;
int m2 = INVALID_VALUE;
int cnt1 = 0;
int cnt2 = 0;
for (int x : nums) {
if (x == m1) cnt1++;
else if (x == m2) cnt2++;
else {
if (cnt1 <= 0) {
m1 = x; cnt1 = 1;
} else if (cnt2 <= 0) {
m2 = x; cnt2 = 1;
} else {
cnt1--;
cnt2--;
}
}
}
cnt1 = 0;
cnt2 = 0;
for (int x : nums) {
if (x == m1) cnt1++;
else if (x == m2) cnt2++;
}
vector<int> res;
if (cnt1 > nums.size() / 3) res.push_back(m1);
if (cnt2 > nums.size() / 3) res.push_back(m2);
return res;
}
};