347 Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
`

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.

  • Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

vector<int> topKFrequent(vector<int>& nums, int k) {
    vector<int> most_freq;
    unordered_map<int, int> hashmap;

    for (int i : nums) {
        // not found, insert new number
        if (hashmap.find(i) == hashmap.end()) {
            hashmap.insert({ { i },{ 1 } });
        }

        // found update frequency
        hashmap.find(i)->second++;
    }

    for (int i = 0; i < k; i++) {
        int max = 0;
        int key = 0;
        for (auto &i : hashmap) {
            if (i.second > max) {
                max = i.second;
                key = i.first;
            }
        }
        hashmap.erase(hashmap.find(key));
        most_freq.push_back(key);
    }

    return most_freq;
}

Last updated