229

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int cand1, cand2, count1, count2;
        cand1 = cand2 = INT_MAX; count1 = count2 = 0;

        for(int num: nums){
            if(cand1 == num){
                count1++;
            }
            else if(cand2 == num){
                count2++;
            }
            else if(count1 == 0){
                count1++;
                cand1 = num;
            }
            else if(count2 == 0){
                count2++;
                cand2 = num;
            }
            else{
                count1--;
                count2--;
            }
        }

        count1 = count2 = 0;
        for(int num: nums){
            if(cand1 == num) count1++;
            if(cand2 == num) count2++;
        }
        vector<int> ans;
        if(count1 > nums.size()/3) ans.push_back(cand1);
        if(count2 > nums.size()/3) ans.push_back(cand2);
        return ans;
    }
};