PattySung

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1:

Input: words = [“i”,“love”,“leetcode”,“i”,“love”,“coding”], k = 2 Output: [“i”,“love”] Explanation: “i” and “love” are the two most frequent words. Note that “i” comes before “love” due to a lower alphabetical order. Example 2:

Input: words = [“the”,“day”,“is”,“sunny”,“the”,“the”,“the”,“sunny”,“is”,“is”], k = 4 Output: [“the”,“is”,“sunny”,“day”] Explanation: “the”, “is”, “sunny” and “day” are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

<解題>


class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        // 創建一個 HashMap 來計算每個單詞的頻率
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        // 創建一個最小堆（優先級佇列）來存儲前 k 高頻單詞
        PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>((a, b) -> {
            int freqA = a.getValue();
            int freqB = b.getValue();
            if (freqA != freqB) {
                return freqA - freqB; //從小排到大
            } else {
                return b.getKey().compareTo(a.getKey()); //字母從小排到大
            }
        });

        // 將每個鍵值對放入最小堆，保持堆的大小不超過 k
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            queue.offer(entry);
            if (queue.size() > k) {
                queue.poll();
            }
        }

        // 將最小堆中的結果取出，並反轉順序，以得到前 k 高頻單詞
        List<String> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            res.add(0, queue.poll().getKey());
        }

        return res;
    }
}

Time: O(N*log(k)) Space: O(N + k)

Leetcode-692. Top K Frequent Words

<解題>