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:

- How many majority elements could it possibly have?
- 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; } };