692. Top K Frequent Words - Medium

前往題目

想法

• 只知道八成需要hashmap，sorting的部分沒有想到什麼好方法

思路

1. Hashmap紀錄每個詞出現的頻率
2. 根據題目條件排序，同樣頻率的詞照首字母排序，然後頻率由高到低排序

Code

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();

        // Count the words
        for (int i = 0; i < words.length; ++i) {
            map.put(words[i], map.getOrDefault(words[i], 0) + 1);
        }

        // Result
        List<String> res = new ArrayList(map.keySet());

        // Sort it lexicographically if 2 words have the same freq.
        Collections.sort(res, (w1, w2) -> 
            map.get(w1).equals(map.get(w2)) ?
            w1.compareTo(w2) : map.get(w2) - map.get(w1)
        );

        return res.subList(0, k);
    }
}

2024/04/24

• 這題考驗的是對java方法的掌握程度😂
• 步驟很直白，但comparator一直都無法完全掌握應該怎麼寫，平時也是少用到，所以要用的時候都得搜尋

相較於原先寫的，這樣的方式好像更好理解一些，但本質上是一樣的

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();

        // Store frequencies
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        // Result
        List<String> res = new ArrayList(map.keySet());

        // Sort it lexicographically if 2 words have the same freq.
        Collections.sort(res, (w1, w2) -> {
            int w1Count = map.get(w1);
            int w2Count = map.get(w2);
        
            // If the counts are equal, then use String.compareTo to lexigraphically compare the strings
            if (w1Count == w2Count) {
                return w1.compareTo(w2);
            } else {  // Else sort by greatest count
                return w2Count - w1Count;
            }
        });
        
        return res.subList(0, k);
    }
}