mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
38 lines
1.6 KiB
Markdown
38 lines
1.6 KiB
Markdown
# [229. Majority Element II](https://leetcode.com/problems/majority-element-ii/)
|
||
# 思路
|
||
给定一个数组，找到所有出现次数大于n/3的元素，其中n为元素个数。
|
||
题意要求返回“所有”满足要求的元素，但我们稍加分析即知满足题意的元素最多两个（反证：若有三个，那这三个元素出现总次数大于3*n/3=n了）。
|
||
|
||
这题其实是[169. Majority Element](https://leetcode.com/problems/majority-element/description/)的升级版，因此解法也是参考[169题解](https://github.com/ShusenTang/LeetCode/blob/master/solutions/169.%20Majority%20Element.md)，
|
||
即摩尔投票法。不过这里有可能有两个结果，所以我们需要保持两个候选结果，遍历完成后再验证活下来的两个候选结果是否满足题意即可。
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
vector<int> majorityElement(vector<int>& nums) {
|
||
vector<int> res;
|
||
|
||
int a = 0, b = 1, cnt1 = 0, cnt2 = 0, n = nums.size();
|
||
for (int &num : nums) {
|
||
if (num == a) cnt1++;
|
||
else if (num == b) cnt2++;
|
||
else if (!cnt1) { a = num; cnt1 = 1; }
|
||
else if (!cnt2) { b = num; cnt2 = 1; }
|
||
else {cnt1--; cnt2--;}
|
||
}
|
||
cnt1 = cnt2 = 0;
|
||
for (int &num : nums) {
|
||
if (num == a) cnt1++;
|
||
else if(num == b) cnt2++;
|
||
}
|
||
// cnt1 = count(nums.begin(), nums.end(), a);
|
||
// cnt2 = count(nums.begin(), nums.end(), b);
|
||
|
||
if (cnt1 > n / 3) res.push_back(a);
|
||
if (cnt2 > n / 3) res.push_back(b);
|
||
return res;
|
||
}
|
||
};
|
||
```
|