# 347. Top K Frequent Elements

• Time: $O(n\log k)$
• Space: $O(n)$
  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 struct T { int num; int freq; T(int num, int freq) : num(num), freq(freq) {} }; class Solution { public: vector topKFrequent(vector& nums, int k) { const int n = nums.size(); vector ans; unordered_map count; auto compare = [](const T& a, const T& b) { return a.freq > b.freq; }; priority_queue, 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; } }; 
  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 33 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 count = new HashMap<>(); Queue minHeap = new PriorityQueue<>((a, b) -> a.freq - b.freq); for (final int num : nums) count.merge(num, 1, Integer::sum); for (Map.Entry 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; } }