347. Top K Frequent Elements - Medium

前往題目

想法

• 利用hashmap儲存數字個數以便快速存取
• 使用priority queue來比較並儲存比較關係

思路

自己的思路

1. hashmap儲存數字個數
2. priority queue儲存比較關係，由小到大，每當pq size超過k的時候就把頭去掉，因為頭是當前最小值，而最終需要的是前k大的

時間複雜度: O(nums.length + nums.length * log (size of map) + k)，大概是這樣，因為加到binary heap需要log n時間。可以簡化為n log n，n是nums的長度
空間: O(n + k)，n是nums的長度

Code

難得自己寫出來的題目

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Store num counts
        Map<Integer, Integer> map = new HashMap();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 小到大
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(
            (a, b) -> map.get(a) - map.get(b)
        );

        // Add elements to the priority queue
        for(Integer key : map.keySet()){
            pq.add(key);
            // 超過k項就刪掉頭，為了節省空間，不用所有數字都存進去
            if (pq.size() > k) pq.poll(); 
        }

        // 結果
        int[] res = new int[k];

        for (int i = 0; i < k; ++i) {
            res[i] = pq.poll();
        }
        return res;
    }
}