LeetCode Note Java 00347：Top K Frequent Elements

發表於 更新於 分類於 ， ， ， 閱讀次數： Disqus： 文章字數： 185 所需閱讀時間 ≈ 1 分鐘

回傳 array 中頻率最高的 k 個元素。

題目

Top K Frequent Elements Medium

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] output = new int[k];
        // 將計數存進 HashMap
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int value : nums) {
            hm.put(value, hm.getOrDefault(value, 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
            (a, b) -> a.getValue() - b.getValue() // Ascending Order
        );
        for (Map.Entry<Integer, Integer> entry : hm.entrySet()) {
            pq.add(entry);
            if (pq.size() > k) {
                pq.poll(); // 將最小的值排除
            }
        }
        for (int i = 0; i < k; i++) {
            output[i] = pq.poll().getKey();
        }
        return output;
    }
}

檢討

若不會特定的資料結構相關組件就要手刻一個類似功能，所以最好趁練習的時候多記一些。

參考資料

Java PriorityQueue

neetcode-gh/leetcode/blob/main/java/347-Top-K-Frequent-Elements.java