Top K Frequent Elements
Given a non-empty array of integers, return thekmost frequent elements.
For example,
Given[1,1,1,2,2,3]
and k = 2, return[1,2]
.
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
Here is a solution.
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
// create hash map and count frequency of all elements O(n) {1:3, 2:2, 3:1}
// then sort the elements by value and get the top K elements
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
return map.entrySet()
.stream()
.sorted((a, b) -> b.getValue() - a.getValue())
.map(entry -> entry.getKey())
.limit(k)
.collect(Collectors.toList());
}
}
Last updated
Was this helpful?