LeetCode 692 Top K Frequent Words

思路

自定义类Pair用于存储String和对应的出现次数。首先遍历一遍所有字符串，将所有字符串和其出现次数先存储在一个hashmap中；然后遍历整个hashmap，在创建pair的同时将其插入一个priority queue中（最小堆）；最后将pq中的所有元素poll出来，然后做一个逆序后输出即可。
【需要自定义优先队列的比较器，因为参与排序的键有2个：freq和str的顺序。其中freq是越高优先级越高，str是越低优先级越高，因此在最小堆中这2个条件分别是freq1-freq2和str2.compareTo(str1)】

代码

class Solution {
    class Pair {
    String str;int freq;public Pair(String str, int freq) {
    this.str = str;this.freq = freq;}}public List<String> topKFrequent(String[] words, int k) {
    Map<String,Integer> freqmap = new HashMap<>();for(String s : words) {
    if(!freqmap.containsKey(s)) {
    freqmap.put(s,0);} else {
    freqmap.put(s,freqmap.get(s) + 1);}}Comparator<Pair> cmp = new Comparator<Pair>() {
    @Overridepublic int compare(Pair p1, Pair p2) {
    if(p1.freq != p2.freq) {
    return p1.freq - p2.freq;}return p2.str.compareTo(p1.str);}};PriorityQueue<Pair> pq = new PriorityQueue<>(k,cmp);for(String s : freqmap.keySet()) {
    Pair pair = new Pair(s,freqmap.get(s));if(pq.size() < k)pq.offer(pair);else if(cmp.compare(pair,pq.peek()) > 0) {
    pq.poll();pq.offer(pair);}}List<String> result = new ArrayList<>();while(!pq.isEmpty()) {
    result.add(pq.poll().str);}Collections.reverse(result);return result;}
}

复杂度分析

时间复杂度O(nlogk), 空间复杂度O(n)