Time Complexity: O(nlog(k)) Space Complexity: O(n)
(int[] nums, int k)
| 5 | * Space Complexity: O(n) |
| 6 | */ |
| 7 | public int[] topKFrequent(int[] nums, int k) { |
| 8 | int[] arr = new int[k]; |
| 9 | HashMap<Integer, Integer> map = new HashMap<>(); |
| 10 | for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1); |
| 11 | PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>( |
| 12 | (a, b) -> |
| 13 | a.getValue() - b.getValue() |
| 14 | ); |
| 15 | for (Map.Entry<Integer, Integer> it : map.entrySet()) { |
| 16 | pq.add(it); |
| 17 | if (pq.size() > k) pq.poll(); |
| 18 | } |
| 19 | int i = k; |
| 20 | while (!pq.isEmpty()) { |
| 21 | arr[--i] = pq.poll().getKey(); |
| 22 | } |
| 23 | return arr; |
| 24 | } |
| 25 | } |
| 26 | |
| 27 | class Solution2 { |