Skip to main content

0347 - Top K Frequent Elements (Medium)

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

Problem Statement​

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= nums.length <= 10^5
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

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

Approach 1: Priority Queue​

When you need to solve something started with "Top K ...", priority queue may possibly be the solution.

We use priority queue to sort the input by their frequency and pop the top element when the queue size is greater than kk. What's left in the queue would be the top kk frequent elements and we just list them out in a reverse order.

Written by @wingkwong
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int n = nums.size();
        if(n == k) return nums;
        map<int, int> m;
        // store the frequency of each number
        for(auto x : nums) m[x]++;
        // define a custom comparator
        auto cmp = [&](int x, int y) {
            return m[x] > m[y];
        };
        // init priority queue with a custom comparator
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        // iterate each number
        for(auto x : m) {
            // add this number
            pq.push(x.first);
            // out of queue size, pop the one with min frequency out
            if(pq.size() > k) {
                pq.pop();
            }
        }
        // construct ans
        vector<int> ans(k);
        for(int i = k - 1; i >= 0; i--) {
            ans[i] = pq.top(); 
            pq.pop();
        }
        return ans;
    }
};