目录
数据流中的第K⼤元素（easy）
题目解析
讲解算法原理
编写代码
前K个⾼频单词（medium）
题目解析
讲解算法原理
编写代码
数据流中的第K⼤元素（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
设计⼀个找到数据流中第k⼤元素的类（class）。注意是排序后的第k⼤元素，不是第k个不同的元素。
请实现KthLargest类：KthLargest(intk,int[]nums)使⽤整数k和整数流nums初始化对象。intadd(intval)将val插⼊数据流nums后，返回当前数据流中第k⼤的元素。
⽰例：输⼊：
["KthLargest","add","add","add","add","add"]
[[3,[4,5,8,2]],[3],[5],[10],[9],[4]]
输出：
[null,4,5,5,8,8]
解释：
KthLargestkthLargest=newKthLargest(3,[4,5,8,2]);
kthLargest.add(3);//return4
kthLargest.add(5);//return5
kthLargest.add(10);//return5
kthLargest.add(9);//return8
kthLargest.add(4);//return8
提⽰：
1<=k<=10^4
0<=nums.length<=10^4
-104<=nums[i]<=10^4
-104<=val<=10^4
最多调⽤add⽅法10^4次题⽬数据保证，在查找第k⼤元素时，数组中⾄少有k个元素
讲解算法原理
解法（优先级队列）：
算法思路：
我相信，看到 TopK 问题的时候，兄弟们应该能⽴⻢想到「堆」，这应该是刻在⻣⼦⾥的记忆。
编写代码
c++算法代码：
class KthLargest
{// 创建⼀个⼤⼩为 k 的⼩跟堆priority_queue<int, vector<int>, greater<int>> heap;int _k;
public:KthLargest(int k, vector<int>& nums) {_k = k;for(auto x : nums){heap.push(x);if(heap.size() > _k) heap.pop();}}int add(int val) {heap.push(val);if(heap.size() > _k) heap.pop();return heap.top();}
};
/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj = new KthLargest(k, nums);* int param_1 = obj->add(val);*/class KthLargest
{// 创建⼀个⼤⼩为 k 的⼩根堆PriorityQueue<Integer> heap;int _k;public KthLargest(int k, int[] nums) {_k = k;heap = new PriorityQueue<>();for(int x : nums){heap.offer(x);if(heap.size() > _k){heap.poll();}}}public int add(int val) {heap.offer(val);if(heap.size() > _k){heap.poll();}return heap.peek();}
}
/*** Your KthLargest object will be instantiated and called as such:* KthLargest obj = new KthLargest(k, nums);* int param_1 = obj.add(val);*/前K个⾼频单词（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个单词列表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(nlogk)时间复杂度和O(n)空间复杂度解决。
讲解算法原理
解法（堆）：
算法思路：
• 稍微处理⼀下原数组：
a. 我们需要知道每⼀个单词出现的频次，因此可以先使⽤哈希表，统计出每⼀个单词出现的频
次；
b. 然后在哈希表中，选出前k⼤的单词（为什么不在原数组中选呢？因为原数组中存在重复的单
词，哈希表⾥⾯没有重复单词，并且还有每⼀个单词出现的频次）
• 如何使⽤堆，拿出前k⼤元素：
a. 先定义⼀个⾃定义排序，我们需要的是前 k ⼤，因此需要⼀个⼩根堆。但是当两个字符串的
频次相同的时候，我们需要的是字典序较⼩的，此时是⼀个⼤根堆的属性，在定义⽐较器的时候需要注意！
▪ 当两个字符串出现的频次不同的时候：需要的是基于频次⽐较的⼩根堆
▪ 当两个字符串出现的频次相同的时候：需要的是基于字典序⽐较的⼤根堆
b. 定义好⽐较器之后，依次将哈希表中的字符串插⼊到堆中，维持堆中的元素不超过 k 个；c. 遍历完整个哈希表后，堆中的剩余元素就是前 k ⼤的元素
编写代码
c++算法代码：
class Solution
{typedef pair<string, int> PSI;struct cmp{bool operator()(const PSI& a, const PSI& b){if(a.second == b.second) // 频次相同，字典序按照⼤根堆的⽅式排列 {return a.first < b.first;}return a.second > b.second;}};
public:vector<string> topKFrequent(vector<string>& words, int k) {// 1. 统计⼀下每⼀个单词的频次unordered_map<string, int> hash;for(auto& s : words) hash[s]++;// 2. 创建⼀个⼤⼩为 k 的堆priority_queue<PSI, vector<PSI>, cmp> heap;// 3. TopK 的主逻辑for(auto& psi : hash){heap.push(psi);if(heap.size() > k) heap.pop();}// 4. 提取结果vector<string> ret(k);for(int i = k - 1; i >= 0; i--){ret[i] = heap.top().first;heap.pop();}return ret;}
};class Solution
{public List<String> topKFrequent(String[] words, int k) {// 1. 统计⼀下每⼀个单词出现的频次Map<String, Integer> hash = new HashMap<>();for(String s : words){hash.put(s, hash.getOrDefault(s, 0) + 1);}// 2. 创建⼀个⼤⼩为 k 的堆PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>((a, b) ->{if(a.getValue().equals(b.getValue())) // 频次相同的时候，字典序按照⼤根堆的⽅式排列{return b.getKey().compareTo(a.getKey());}return a.getValue() - b.getValue();});// 3. TopK 的主逻辑for(Map.Entry<String, Integer> e : hash.entrySet()){heap.offer(new Pair<>(e.getKey(), e.getValue()));if(heap.size() > k){heap.poll();}}// 4. 提取结果List<String> ret = new ArrayList<>();while(!heap.isEmpty()){ret.add(heap.poll().getKey());}// 逆序数组Collections.reverse(ret);return ret;}
}
