文章目錄

• Top K Frequent Words 前K個高頻單詞
• 思路
• Tag

Top K Frequent Words 前K個高頻單詞

給一非空的單詞清單，傳回前 k 個出現次數最多的單詞。

傳回的答案應該按單詞出現頻率由高到低排序。如果不同的單詞有相同出現頻率，按字母順序排序。

輸入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
輸出: ["i", "love"]
解析: "i" 和 "love" 為出現次數最多的兩個單詞，均為2次。
    注意，按字母順序 "i" 在 "love" 之前。
 
           

思路

通過堆排序，主要設定排序的規則

public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            String s = words[i];
            map.put(s,map.getOrDefault(s,0)+1);
        }
        PriorityQueue<String> pq = new PriorityQueue<String>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                Integer a = map.get(o1);
                Integer b = map.get(o2);
                int res =0;
                if(a.equals(b)){
                    res = o2.compareTo(o1);
                }
                else {
                    res = a -b;
                }
                return res;
            }
        });
        for (Map.Entry<String, Integer> item : map.entrySet()) {
            pq.offer(item.getKey());
            if(pq.size()>k){
                pq.poll();
            }
        }
        List<String> ans = new ArrayList<>();
        while(!pq.isEmpty()){
            ans.add(0,pq.poll());
        }
        return ans;
    }
           

Tag

heap