LeetCode 692. 前K个高频单词 hashmap排序

小咪咪 2023-01-23 01:56 229阅读 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
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：  
1、利用hashmap统计所有字符串的出现次数；  
2、建立Arraylist存储hashmap的entry；  
3、利用collections工具类对ArrayList进行排序，排序规则：

a）判断两个entry的出现次数是否相同；
    	b）次数相同，比较两个字符串的字典序，按字典序进行排序；
    	c）次数不同，则直接按照出现次数从小到大排序；

4、建立结果链表，将ArrayList的前k项进行输出即可。

import java.util.Map.Entry;
    class Solution {
        
        public List<String> topKFrequent(String[] words, int k) {
        
        	Map<String, Integer> map=new HashMap<String, Integer>();
        	for(int i=0;i<words.length;i++) {
        
        		map.put(words[i], map.getOrDefault(words[i], 0)+1);
        	}
        	List<Map.Entry<String,Integer>> list=new ArrayList<Map.Entry<String,Integer>>(map.entrySet());
        	Collections.sort(list, new Comparator<Map.Entry<String,Integer>>() {
        
    			@Override
    			public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
        
    				// TODO 自动生成的方法存根
    				if(o1.getValue()==o2.getValue()) return o1.getKey().compareTo(o2.getKey());
    				return o2.getValue()-o1.getValue();
    			}
    		});
        	 List<String> res=new ArrayList<String>();
        	 for(int i=0;i<k;i++) {
        
        		 res.add(list.get(i).getKey());
        	 }
        	 return res;
        }
    }