# [leetcode] Majority Element II

Given an integer array of size n, find all elements that appear more than `⌊ n/3 ⌋` times. The algorithm should run in linear time and in O(1) space.

Hint:

1. How many majority elements could it possibly have?
2. Do you have a better hint? Suggest it!

Vote for the majority.

```class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int a = 0, b = 0;
vector<int> ans;
int counta = 0, countb = 0;
for(auto num: nums){
if(num == a){
counta++;
}
else if(num == b){
countb++;
}
else{
//a b are not the same as num
if(counta == 0){
a = num;
counta = 1;
}
else if(countb == 0){
b = num;
countb = 1;
}
else{
//a b counts are not 0
counta--;
countb--;
}
}
}
int finalCounta = 0, finalCountb = 0;
for(auto num: nums){
if(num == a) finalCounta++;
else if(num == b) finalCountb++;
}
if(finalCounta > nums.size() / 3) ans.push_back(a);
if(finalCountb > nums.size() / 3) ans.push_back(b);
return ans;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.