infrastructureDataStructure8

发表于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/top-k-frequent-words/]

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

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

示例 1：

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

示例 2：

1
2
3
4
输入: ["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. 输入的单词均由小写字母组成。

扩展练习：

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

算法描述

使用哈希表将字符串数组遍历一遍，对每个单词进行计数，完成后，使用优先队列，将哈希表中的结果添加至优先队列，在此之前需要重载一个小于号，这样就会按照从大到小的顺序在优先队列中，然后遍历前k个字符串，返回结果即可；

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    struct word{
        string str;
        int count;
        bool operator < (const word& res) const
        {
            if(count == res.count) return str > res.str;
            return count < res.count;
        }
    };
    map<string,int> Hash;
    vector<string> topKFrequent(vector<string>& words, int k) {
        Hash.clear();
        for(int i = 0; i < words.size(); i++) Hash[words[i]]++;
        map<string,int>:: iterator ite = Hash.begin();
        priority_queue<word> q;
        for(;ite != Hash.end(); ite++){
            word w;
            w.str = (*ite).first;
            w.count = (*ite).second;
            q.push(w);
        }
        vector<string> res;
        for(int i = 0; i < k; i++){
            res.push_back(q.top().str);
            q.pop();
        }
        return res;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> hm = new HashMap<String,Integer>();
        for(int i=0;i<words.length;i++){
             hm.put(words[i],hm.getOrDefault(words[i],0)+1);
        }
		PriorityQueue<String> pq = new PriorityQueue<>(k,new Comparator<String>(){
             public int compare(String s1,String s2){
                if(hm.get(s1).equals(hm.get(s2))){
                    return s2.compareTo(s1);
                }
                return hm.get(s1).compareTo(hm.get(s2));
            }
        });
        for(String s : hm.keySet()){
            if(pq.size()<k){
                pq.add(s);
            }else if(pq.comparator().compare(s, pq.peek())>0){
                pq.poll();
                pq.add(s);
            }
        }
        String[] ans = new String[k];
        for(int i=k-1;i>=0;i--){
            ans[i] = pq.poll();
        }
        return Arrays.asList(ans);
    }
}