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

majority-element-ii.cpp

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int count1 = 0;
        int count2 = 0;
        int candidate1 = -1;
        int candidate2 = -1;
        for (int num : nums) {
            if (num == candidate1) {
                count1 += 1;
            } else if (num == candidate2) {
                count2 += 1;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1 -= 1;
                count2 -= 1;
            }
        }
        // get actual total counts
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            count1 += num == candidate1;
            count2 += num == candidate2;
        }
        vector<int> top_elements;
        if (count1 * 3 > nums.size()) top_elements.push_back(candidate1);
        if (count2 * 3 > nums.size()) top_elements.push_back(candidate2);
        return top_elements;
    }
};