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;
    }
}

2025/04/12

以下是bucket sort

1. 每個bucket儲存同樣數量的數字（如果有1,2，那他們都會被存在數量為一的桶子裡），這樣只要n個桶子就好，n是input數量，因為最多就是整個陣列都同一個數字
2. 把數字都按照這個規則存進去桶子裡後就可以從後往前循環直到拿到k個數字就可以回傳了

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Store counts
        Map<Integer, Integer> count = new HashMap();
        // Bucket (by frequencies)
        List<Integer>[] bucket = new List[nums.length + 1];

        // Store counts
        for (int i = 0; i < nums.length; ++i) {
            count.put(nums[i], count.getOrDefault(nums[i], 0) + 1);
        }

        // Init. buckets
        for (int i = 0; i < bucket.length; ++i) {
            bucket[i] = new ArrayList();
        }

        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            // Find the bucket of the count and put in the number
            bucket[entry.getValue()].add(entry.getKey());
        }

        // Build the result
        int index = 0;
        int[] res = new int[k];
        for (int i = bucket.length - 1; i > 0 && index < k; --i) {
            for (int num : bucket[i]) {
                res[index] = num;
                ++index;
                // Result obtained
                if (index == k) return res;
            }
        }

        return res;
    }
}