347. Top K Frequent Elements

• Difficulty: Medium

• Topics: Hash Table, Heap

• Similar Questions:

  • Word Frequency

  • Kth Largest Element in an Array

  • Sort Characters By Frequency

  • Split Array into Consecutive Subsequences

  • Top K Frequent Words

  • K Closest Points to Origin

Problem:

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

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Input: nums = [1], k = 1
Output: [1]

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.

Solutions:

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

        for (auto num : nums) {
            ++counts[num];
        }

        set<pair<int, int>> topKIndex;

        for (auto it = counts.begin(); it != counts.end(); ++it) {
            topKIndex.insert({it->second, it->first});
            if (topKIndex.size() > k) {
                topKIndex.erase(topKIndex.begin());
            }
        }

        vector<int> ret;
        for (auto it = topKIndex.rbegin(); it != topKIndex.rend(); ++it) {
            ret.push_back(it->second);
        }

        return ret;
    }
private:
    unordered_map<int, int> counts;
};