229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

// Moore Voting Method
vector<int> majorityElement(vector<int>& nums) { // time: O(n); space: O(1)
    int n = nums.size(), cand1 = 0, cand2 = 0, cnt1 = 0, cnt2 = 0;
    vector<int> res;
    for (int num : nums) {
        if (num == cand1) ++cnt1;
        else if (num == cand2) ++cnt2;
        else if (cnt1 == 0) {
            cand1 = num;
            ++cnt1;
        } else if (cnt2 == 0) {
            cand2 = num;
            ++cnt2;
        } else {
            --cnt1, --cnt2;
        }
    }
    // Reset counters
    cnt1 = 0, cnt2 = 0;
    for (int num : nums) {
        if (num == cand1) ++cnt1;
        else if (num == cand2) ++cnt2;
    }
    if (cnt1 > n / 3) res.push_back(cand1);
    if (cnt2 > n / 3) res.push_back(cand2);
    return res;
}

169. Majority Element