Leetcode 692. 前K个高频单词

缺乏、安全感 2022-08-31 13:21 123阅读 0赞

#### 题目重述 ####

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

##### 示例 1： #####

输入: \[“i”, “love”, “leetcode”, “i”, “love”, “coding”\], k = 2  
输出: \[“i”, “love”\]  
解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。  
注意，按字母顺序 “i” 在 “love” 之前。

##### 示例 2： #####

输入: \[“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”\], k = 4  
输出: \[“the”, “is”, “sunny”, “day”\]  
解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，  
出现次数依次为 4, 3, 2 和 1 次。

##### 注意： #####

假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。  
输入的单词均由小写字母组成。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/top-k-frequent-words  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

HashMap映射存出现次数

对HashMap自定义排序即可，无法直接排序，需要将其先转化为List

#### Java实现 ####

class Solution {
        
        public List<String> topKFrequent(String[] words, int k) {
        
            Map<String,Integer> m = new HashMap<>();
            for (int i = 0; i < words.length; i++) {
        
                m.put(words[i],m.getOrDefault(words[i],0)+1);
            }
            List<Map.Entry<String,Integer>> list = new ArrayList<Map.Entry<String,Integer>>(m.entrySet());
            Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
        
                @Override
                public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
        
                    if(o1.getValue().intValue() == o2.getValue().intValue())
                    {
        
                        return o1.getKey().compareTo(o2.getKey());
                    }
                    return o2.getValue().compareTo(o1.getValue());
                }
            });
            List<String> result = new ArrayList<>();
            for (int i = 0; i < k; i++) {
        
                result.add(list.get(i).getKey());
            }
            return result;
        }
    }

解答成功:
    执行耗时:6 ms,击败了98.90% 的Java用户
    内存消耗:38.8 MB,击败了25.22% 的Java用户