Top K Frequent Elements
Post
Cancel

# LeetCode #347: Top K Frequent Elements (C/C++).

medium

source: https://leetcode.com/problems/top-k-frequent-elements
C/C++ Solution to LeetCode problem 347. Top K Frequent Elements.

## Problem

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

## Examples

### Example 1:

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

### Example 2:

Input: nums = , k = 1
Output: 

## Constraints

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 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.

## Solution

To solve this problem we will use a hash table to get the frequency of each number.
Then we will use a max heap, in this case a priority queue that simplifies the way to handle the max heap.

We have to sort the words by frequency (highger first).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public: typedef pair<int, int> num_freq; struct compare { bool operator()(num_freq& a, num_freq& b) { return a.second > b.second; } }; vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> result; unordered_map<int, int> m; priority_queue<num_freq, vector<num_freq>, compare> pq; for (int i=0; i<nums.size(); i+=1) m[nums[i]] += 1; for (auto const& [key, value]: m) { pq.push({key, value}); if (pq.size() > k) pq.pop(); } while (!pq.empty()) { result.push_back(pq.top().first); pq.pop(); } return result; } };