Top k elements with most occurrences
Written on January 19, 2016
Tweet
Find k elements within a array with most occurrences.
public class Solution {
public static void main(String[] args) {
int[] nums = {1,1,2,2,3,3,3,4,5,6,6,6,6,6,7,7,7,8,8,8,8,9,10,11,12,13,14,15,15};
System.out.println(get(nums, 3));
}
public static List<Integer> get(int[] nums, int k) {
List<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0 || k == 0) return result;
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
System.out.println(map);
PriorityQueue<Integer> pq = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return map.get(o1) - map.get(o2);//不用造class来储存值和次数
}
});
for (int key : map.keySet()) {
if (pq.size() == k) {
if (map.get(pq.peek()) < map.get(key)) {
pq.poll();
pq.offer(key);
}
} else {
pq.offer(key);
}
}
while (!pq.isEmpty()) {
result.add(pq.poll());
}
return result;
}
}