Programming

Leetcode-347. Top K Frequent Elements

By PattySung 31 July 2023
Leetcode-347. Top K Frequent Elements

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

Example 1:

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

Example 2:

Input: nums = [1], k = 1
Output: [1]

<解題> 解法一: bucket 排序


class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        List<List<Integer>> buckets = new ArrayList<>();
        buckets.add(new ArrayList<>());

        HashMap<Integer, Integer> counts = new HashMap<>();

        for(int num: nums){
            counts.put(num, counts.getOrDefault(num, 0) + 1);
            buckets.add(new ArrayList<>());
        }

        // 按照頻率把數字丟到桶子裡
        for(int num: counts.keySet()){
            int count = counts.get(num);
            buckets.get(count).add(num);
        }

        int[] res = new int[k];
        for(int i = buckets.size()-1 ; i > 0 ; i--){
            if(k <= 0) return res;
            if(buckets.get(i).size() == 0) continue;
            for(int num : buckets.get(i)){
                res[--k] = num;
            }
        }
        return res;
    }
}

Time: O(n) Space: O(n)

merge用法

前面merge的寫法，可改寫成如下：

  1. count.getOrDefault(num, 0) + 1: 使用 getOrDefault 方法來取得 num 鍵對應的值，如果鍵不存在，則使用預設值 0。然後將這個值加 1，以計算元素的出現次數

  2. count.put(num, … ): 使用 put 方法將新的計數值放入 count Map 中，這樣就更新了元素的出現次數。


Map<Integer, Integer> count = new HashMap<>();

for (int num : nums) {
    count.put(num, count.getOrDefault(num, 0) + 1);
}

解法二: HashMap


class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>(); 

        HashMap<Integer, Integer> map = new HashMap<>(); 
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1); 
        }

        // 創建一個最大堆（優先級佇列），按頻率由大到小排序
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            queue.offer(entry); // 將哈希表中的鍵值對放入最大堆
        }

        for (int i = 0; i < k; i++) {
            res.add(queue.poll().getKey()); // 依次取出頻率最高的 k 個數字並加入結果列表
        }

        int[] arr = new int[res.size()]; 
        for (int i = 0; i < arr.length; i++) {
            arr[i] = res.get(i); 
        }
        return arr; 
    }
}