347. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/

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]

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

It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.

You can return the answer in any order.

Solution

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> counter;
        auto comparator = [](const auto &a, const auto &b) {
            return a.second > b.second;
        };
        priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(comparator)> min_heap(comparator);
        counter.reserve(nums.size());
        for (const auto& n: nums) ++counter[n];
        for (const auto& pair: counter) {
            if (min_heap.size() < k) {
                min_heap.push(pair);
                continue;
            } 
            if (min_heap.top().second < pair.second) {
                min_heap.pop();
                min_heap.push(pair);
            }
        }
        vector<int> frequent_list;
        frequent_list.reserve(k);
        while (!min_heap.empty()) {
            frequent_list.push_back(min_heap.top().first);
            min_heap.pop();
        } 
        return frequent_list;
    }
};

• #heap

• #hash