Leetcode刷题100天—692. 前K个高频单词(优先队列)—day17

短命女 2022-09-11 03:18 291阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210824124023954][]

给一非空的单词列表，返回前 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 次。

**注意：**

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

**扩展练习：**

尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

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

package 优先队列;
    
    
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.PriorityQueue;
    
    public class _692_前K个高频单词 { 
    // 1. 通过哈希获取词频 o(n)2. 通过优先队列排序o(mlogk) （大顶堆）3.返回遍历输出o(k) 
        public List<String> topKFrequent(String[] words, int k) { 
        	List<String> res=new LinkedList<String>();
        	Map<String, Integer> map=new HashMap<String, Integer>();
    // for循环遍历统计
        	int c=0;
        	String w[] = new String[words.length];
        	for(String word:words) { 
        		map.put(word, map.getOrDefault(word, 0)+1);
        		
        	}
            
        
            // System.out.print(map);
    // 优先队列
        	PriorityQueue<Data> queue=new PriorityQueue<>(new Comparator<Data>() { 
        		public int compare(Data o1,Data o2) { 
                    // 如果两个值相等，则按照字母顺序排列，不相等就用大顶堆
        				return o2.getV()==o1.getV()?o1.getK().compareTo(o2.getK()):o2.getV()-o1.getV();//大顶堆
        		}
    		});
    // 将map中的键值循环遍历到队列中
        	for(Map.Entry<String, Integer> entry:map.entrySet()) { 
        		queue.offer(new Data(entry.getKey(),entry.getValue()));
        	}
    // 循环遍历出队前k个值
        	for(int i=0;i<k;i++) { 
        		
        		Data data= (Data)queue.poll();
    // 调用函数
                // System.out.print(data.getK());
        		res.add(data.getK());
        	}
            // Collections.reverse(res);
        	return res;
        			
        }
    // 设置数据类Data
        public class Data{ 
        	String key;
        	int value;
        	public Data(String key,int value) { 
    			this.key=key;
    			this.value=value;
    		}
    // 设置获取key函数
        	public String getK() { 
        		return this.key;
        	}
        	public int getV() { 
        		return this.value;
        	}
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210824124023954]: /images/20220828/897fce857fe04ce89321bf4cb0933fe3.png