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;
    }
};