private static List<Integer> topKFrequent(int[] nums, int k) {
The specification as described explains why the input uses int[]
, but doesn't seem to fix the return type. Why List<Integer>
? I can see an argument for int[]
(consistency with the input), and I can see an argument for Set<Integer>
(encodes the constraint that the returned values will be distinct), but I can't see a reason for List<Integer>
.
// freq map
Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
for (int n : nums) {
freq.put(n, freq.getOrDefault(n, 0) + 1);
}
Nice use of the recent API additions.
// bucket sort on freq
List<Integer>[] bucket = new ArrayList[nums.length + 1];
for (int i = 0; i < bucket.length; i++)
bucket[i] = new ArrayList<>();
for (int key : freq.keySet()) {
bucket[freq.get(key)].add(key);
}
Why the inconsistency over whether to use {}
for a single statement for
body?
The bucket sort is time-efficient, but as implemented it's not very memory-efficient. Have you considered doing a first pass over freq
to find the maximum frequency, so that bucket
can be allocated to the smallest possible size? Have you considered allocating bucket[i] = new ArrayList<>();
on demand, the first time you encounter a frequency of i
?
Iterating over a map's keySet()
and then calling into the map is inefficient. When HashMap
works well it's only a small constant factor inefficiency, but to illustrate the problem suppose that you were using TreeMap
. Then keySet()
takes \$O(m)\$ time (where \$m\$ is the number of entries in the map), but the \$m\$ calls to get()
take a total of \$O(m \lg m)\$ time. Iterating over entrySet()
takes \$O(m)\$ time and saves the extra work of looking up the entries by key.
// gather result
List<Integer> res = new ArrayList<>();
for (int i = bucket.length - 1; i >= 0; i--) {
res.addAll(bucket[i]);
if (res.size() >= k)
break;
}
What about corner cases? If there are fewer than k
distinct values in nums
, should the method throw an exception or return all of the distinct values? If res.size() > k
should you discard some elements from the smallest bucket in order to return only k
elements? The specification as quoted is unclear, so maybe you should push for clarification.