文章目录一、题目解析1. 数据流中的第 K 大元素TOP-K问题2. 前K个高频单词3. 数据流的中位数利用两个堆一、题目解析1. 数据流中的第 K 大元素TOP-K问题703. 数据流中的第 K 大元素题目描述设计一个找到数据流中第 k 大元素的类class。注意是排序后的第 k 大元素不是第 k 个不同的元素。请实现 KthLargest 类1KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。2int add(int val) 将 val 插入数据流 nums 后返回当前数据流中第 k 大的元素。示例 1输入[ “KthLargest”, “add”, “add”, “add”, “add”, “add” ][ [ 3, [4, 5, 8, 2] ], [3], [5], [10], [9], [4] ]输出[ null, 4, 5, 5, 8, 8 ]解释KthLargest kthLargest new KthLargest( 3, [4, 5, 8, 2] );kthLargest.add(3); // 返回 4kthLargest.add(5); // 返回 5kthLargest.add(10); // 返回 5kthLargest.add(9); // 返回 8kthLargest.add(4); // 返回 8示例 2输入[ “KthLargest”, “add”, “add”, “add”, “add” ][ [4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9] ]输出[ null, 7, 7, 7, 8 ]解释KthLargest kthLargest new KthLargest( 4, [7, 7, 7, 7, 8, 3] );kthLargest.add(2); // 返回 7kthLargest.add(10); // 返回 7kthLargest.add(9); // 返回 7kthLargest.add(9); // 返回 8提示0 nums.length 10^41 k nums.length 1-10^4 nums[i] 10^4-10^4 val 10^4最多调用 add 方法 10^4 次代码演示classKthLargest{int_k;// 维持一个元素个数最大为_k的小堆// 当元素个数为_k时第_k大的元素就是堆顶元素priority_queueint,vectorint,greaterintpri;public:KthLargest(intk,vectorintnums){_kk;for(autoit:nums){if(pri.size()_k)pri.push(it);else{if(itpri.top()){pri.push(it);pri.pop();// 维持小堆的元素个数为_K}}}}intadd(intval){if(pri.size()_k)pri.push(val);else{if(valpri.top()){pri.push(val);pri.pop();// 维持小堆的元素个数为_K}}// 根据题目提示1 k nums.length 1// 推断在小堆插入一次元素后小堆元素个数绝对稳定在_k个returnpri.top();}};/** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj new KthLargest(k, nums); * int param_1 obj-add(val); */2. 前K个高频单词692. 前K个高频单词题目描述给定一个单词列表 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 5001 words[i].length 10words[i] 由小写英文字母组成。k 的取值范围是 [1, 不同 words[i] 的数量]进阶尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。代码演示classSolution{public:classgreater{public:booloperator()(pairstring,intpa1,pairstring,intpa2){if(pa1.secondpa2.second)// 当不同的单词有相同出现频率{returnpa1.firstpa2.first;// 字符串比较 按照大堆排序(也就是 字典序按照小堆排序)}returnpa1.secondpa2.second;// 单词出现频率 按照小堆排序}};vectorstringtopKFrequent(vectorstringwords,intk){// 统计每种单词出现的次数unordered_mapstring,inthash;for(autoword:words)hash[word];// 维持k个元素数量的小堆priority_queuepairstring,int,vectorpairstring,int,greaterpri;for(autopair_word:hash){pri.push(pair_word);if(pri.size()k){pri.pop();}}// 提取结果vectorstringvec_str(k, );for(intik-1;i0;i--){vec_str[i]pri.top().first;pri.pop();}returnvec_str;}};3. 数据流的中位数利用两个堆295. 数据流的中位数题目描述中位数是有序整数列表中的中间值。如果列表的大小是偶数则没有中间值中位数是两个中间值的平均值。例如 arr [2,3,4] 的中位数是 3 。例如 arr [2,3] 的中位数是 (2 3) / 2 2.5 。实现 MedianFinder 类:1MedianFinder() 初始化 MedianFinder 对象。2void addNum(int num) 将数据流中的整数 num 添加到数据结构中。3double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。示例 1输入[ “MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian” ][ [ ], [1], [2], [ ], [3], [ ] ]输出[ null, null, null, 1.5, null, 2.0 ]解释MedianFinder medianFinder new MedianFinder();medianFinder.addNum(1); // arr [1]medianFinder.addNum(2); // arr [1, 2]medianFinder.findMedian(); // 返回 1.5 ((1 2) / 2)medianFinder.addNum(3); // arr[1, 2, 3]medianFinder.findMedian(); // return 2.0提示:-10^5 num 10^5在调用 findMedian 之前数据结构中至少有一个元素最多 5 * 10^4 次调用 addNum 和 findMedian代码实现classMedianFinder{public:// 左侧大根堆priority_queueint,vectorint,lessintpri_left;// 左侧小根堆priority_queueint,vectorint,greaterintpri_right;MedianFinder(){}voidaddNum(intnum){if(pri_left.size()pri_right.size()){if(pri_left.size()0)pri_left.push(num);else{if(numpri_left.top())pri_left.push(num);else{pri_right.push(num);pri_left.push(pri_right.top());pri_right.pop();}}}else{if(numpri_left.top())pri_right.push(num);else{pri_left.push(num);pri_right.push(pri_left.top());pri_left.pop();}}}doublefindMedian(){doublemid;if(pri_left.size()pri_right.size())mid(pri_left.top()pri_right.top())/2.0;elsemidpri_left.top();returnmid;}};/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj new MedianFinder(); * obj-addNum(num); * double param_2 obj-findMedian(); */