229 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.

vector<int> majorityElement(vector<int> &elements) 
{
    int n_over_3 = elements.size() / 3;

    unordered_map<int,int> int_freq;
    for (int i = 0; i < elements.size(); i++) {
        if (int_freq.find(elements.at(i)) != int_freq.end()) {
            int_freq[elements.at(i)]++;
        }
        else {
            int_freq.insert(make_pair(elements.at(i), 1));
        }
    }

    vector<int> majority_elements;
    for (auto i : int_freq) {
        if (i.second > n_over_3) {
            majority_elements.push_back(i.first);
        }
    }

    return majority_elements;
}

Last updated