Time Complexity: O(n) Space Complexity: O(n)
(int[] numbers, int k)
| 31 | * Space Complexity: O(n) |
| 32 | */ |
| 33 | public int[] topKFrequent(int[] numbers, int k) { |
| 34 | HashMap<Integer, Integer> map = new HashMap<>(); |
| 35 | for (int number : numbers) map.put( |
| 36 | number, |
| 37 | map.getOrDefault(number, 0) + 1 |
| 38 | ); |
| 39 | |
| 40 | int size = map.size(); |
| 41 | int[] keys = new int[size]; |
| 42 | int i = 0; |
| 43 | for (int key : map.keySet()) keys[i++] = key; |
| 44 | |
| 45 | select(keys, map, 0, size - 1, size - k); |
| 46 | return Arrays.copyOfRange(keys, size - k, size); |
| 47 | } |
| 48 | |
| 49 | // Modified implementation of Hoare's selection algorithm: |
| 50 |