# 229. Majority Element II

Given an integer array of size  n , find all elements that appear more than `⌊ n/3 ⌋` times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

``````Input: [3,2,3]
Output: [3]
``````

Example 2:

``````Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
``````

``````class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> res;
int a = 0, b = 0, cnt1 = 0, cnt2 = 0, n = nums.size();
for (int num : nums) {
if (num == a) ++cnt1;
else if (num == b) ++cnt2;
else if (cnt1 == 0) { a = num; cnt1 = 1; }
else if (cnt2 == 0) { b = num; cnt2 = 1; }
else { --cnt1; --cnt2; }
}
cnt1 = cnt2 = 0;
for (int num : nums) {
if (num == a) ++cnt1;
else if (num == b) ++cnt2;
}
if (cnt1 > n / 3) res.push_back(a);
if (cnt2 > n / 3) res.push_back(b);
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/229

Majority Element

Check If a Number Is Majority Element in a Sorted Array

https://leetcode.com/problems/majority-element-ii/

https://leetcode.com/problems/majority-element-ii/discuss/63500/JAVA-Easy-Version-To-Understand!!!!!!!!!!!!

https://leetcode.com/problems/majority-element-ii/discuss/63520/Boyer-Moore-Majority-Vote-algorithm-and-my-elaboration

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation