安徽省建设造价网站,杭州哪家网站建设公司好,上海建筑信息平台,网络培训挂机软件题目
给定一个单词列表 words 和一个整数 k #xff0c;返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率#xff0c; 按字典顺序 排序。
示例 1#xff1a;
输入: words [i, love, …题目
给定一个单词列表 words 和一个整数 k 返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率 按字典顺序 排序。
示例 1
输入: words [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 words.length 500 1 words[i] 10 words[i] 由小写英文字母组成。 k 的取值范围是 [1, 不同 words[i] 的数量]
进阶尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。 思路
前k个高频元素
找大用小。
用Map扫描集合将每个单词及出现的频率存入Map中。声明一个基于最小堆的优先级队列传入比较器。题目要求默认按出现频次大小排序频次相同再按字典排序。用String默认的compareTo方法即可String默认实现了Comparable基于字母的字典序比较依次出队列找到前k个高频单词。代码
class Solution {public ListString topKFrequent(String[] words, int k) {//1.扫描原数组将每个单词及出现的次数存储在Map中MapString, Integer cnt new HashMapString, Integer();for (String word : words) {cnt.put(word, cnt.getOrDefault(word, 0) 1);}//2.扫描Map集合将前k个出现频次最高的入优先级队列最小堆//向优先级队列中传入一个比较器PriorityQueueMap.EntryString, Integer pq new PriorityQueueMap.EntryString, Integer(new ComparatorMap.EntryString, Integer() {public int compare(Map.EntryString, Integer entry1, Map.EntryString, Integer entry2) {return entry1.getValue() entry2.getValue() ? entry2.getKey().compareTo(entry1.getKey()) : entry1.getValue() - entry2.getValue();}});//将每一个字符串插入到优先队列中如果优先队列的大小超过了 k那么就将优先队列顶端元素弹出。这样最终优先队列中剩下的 k 个元素就是前 k 个出现次数最多的单词。for (Map.EntryString, Integer entry : cnt.entrySet()) {pq.offer(entry);if (pq.size() k) {pq.poll();}}//3.依次出队列找到前k个高频单词。ListString ret new ArrayListString();//取大用小每次从最小堆中堆顶取得到的前k个高频单词的频率是从小到大的while (!pq.isEmpty()) {ret.add(pq.poll().getKey());}//将ret集合进行反转这样就实现找到前k个高频单词的频率是从大到小的Collections.reverse(ret);return ret;}
}
