## Top K Frequent Elements

• Time:O(n\log k)
• Space:O(n)

## C++

``````struct T {
int num;
int freq;
T(int num, int freq) : num(num), freq(freq) {}
};

class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
const int n = nums.size();
vector<int> ans;
unordered_map<int, int> count;
auto compare = [](const T& a, const T& b) { return a.freq > b.freq; };
priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);

for (const int num : nums)
++count[num];

for (const auto& [num, freq] : count) {
minHeap.emplace(num, freq);
if (minHeap.size() > k)
minHeap.pop();
}

while (!minHeap.empty())
ans.push_back(minHeap.top().num), minHeap.pop();

return ans;
}
};
``````

## JAVA

``````class T {
public int num;
public int freq;
public T(int num, int freq) {
this.num = num;
this.freq = freq;
}
}

class Solution {
public int[] topKFrequent(int[] nums, int k) {
final int n = nums.length;
int[] ans = new int[k];
Map<Integer, Integer> count = new HashMap<>();
Queue<T> minHeap = new PriorityQueue<>((a, b) -> a.freq - b.freq);

for (final int num : nums)
count.merge(num, 1, Integer::sum);

for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
final int num = entry.getKey();
final int freq = entry.getValue();
minHeap.offer(new T(num, freq));
if (minHeap.size() > k)
minHeap.poll();
}

for (int i = 0; i < k; ++i)
ans[i] = minHeap.poll().num;

return ans;
}
}
``````