Majority Element II

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.

Solution: Boyer-Moore Majority Vote

The essential concepts is you keep a counter for the majority number X. If you find a number Y that is not X, the current counter should deduce 1.

And since the requirement is finding the majority for more than n/3, the answer would be less than or equal to two numbers.

So we can modify the algorithm to maintain two counters for two majorities.

vector<int> majorityElement(vector<int>& nums) {
    int count1 = 0, count2 = 0, candidate1, candidate2;
    std::vector<int> res;

    for (auto num:nums) {
        if (candidate1 == num) {
            count1++;
        } else if (candidate2 == num) {
            count2++;
        } else if (count1 == 0) {
            candidate1 = num, count1++;
        } else if (count2 == 0) {
            candidate2 = num, count2++;
        } else {
            count1--, count2--;
        }
    }

    count1 = count2 = 0;
    for (auto num:nums) {
        if (num == candidate1) count1++;
        if (num == candidate2) count2++;
    }

    if (count1 > nums.size()/3) res.push_back(candidate1);
    if (count2 > nums.size()/3) res.push_back(candidate2);
    return res;
}