首页 > itarticle > [leetcode] problem 347 – top k frequent elements

[leetcode] problem 347 – top k frequent elements

admin 11月 13, 2020 0

Given a non-empty array of integers, return the k most frequent elements.

Example

No.1

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

No.2

Input: nums = [1], k = 1

Output: [1]

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.

Code

public List<Integer> (int[] nums, int k) {
    List<Integer> result = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
        
        public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
            return o1.getValue() - o2.getValue();
        }
    });

    for (int num : nums)
        map.put(num, map.getOrDefault(num, 0) + 1);

    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        if (minHeap.size() < k)
            minHeap.offer(entry);
        else if (entry.getValue() > minHeap.peek().getValue()) {
            minHeap.poll();
            minHeap.offer(entry);
        }
    }

    while (!minHeap.isEmpty())
        result.add(minHeap.poll().getKey());

    return result;
}