番禺网站建设效果,企业263邮箱登录入口,深圳建站公司是国企吗,河南省新闻头条最新消息#x1f525;#x1f525; 欢迎来到小林的博客#xff01;#xff01; #x1f6f0;️博客主页#xff1a;✈️林 子 #x1f6f0;️博客专栏#xff1a;✈️ 小林的算法笔记 #x1f6f0;️社区 :✈️ 进步学堂 欢迎来到小林的博客 ️博客主页✈️林 子 ️博客专栏✈️ 小林的算法笔记 ️社区 :✈️ 进步学堂 ️欢迎关注点赞收藏✍️留言 目录 703. 数据流中的第 K 大元素692. 前K个高频单词295. 数据流的中位数 703. 数据流中的第 K 大元素
题目链接703. 数据流中的第 K 大元素
题目描述
设计一个找到数据流中第 k 大元素的类class。注意是排序后的第 k 大元素不是第 k 个不同的元素。
请实现 KthLargest 类
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。int add(int val) 将 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]解释
KthLargest kthLargest new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8提示
1 k 1040 nums.length 104-104 nums[i] 104-104 val 104最多调用 add 方法 104 次题目数据保证在查找第 k 大元素时数组中至少有 k 个元素
解题思路 这一题是典型的topK问题第K大我们可以建小堆。第K小我们可以建大堆。为什么要这样呢因为建小堆的话我们的堆顶就是最小的。我Top一个后新的堆顶就是倒数第二小的。当我们的堆只有的元素只有K个的时候。那么堆顶的元素就是 nums.size - k小的。反过来就是第K大的。nums这里指的是整个数组。
假设整个数组的大小为 7 k 为6。 那么当堆的大小为6时堆顶的元素就是 nums.size - 1(nums.size - heap.size)。也就是第6大的数。所以TOPK问题找第K大建小堆找第K小建大堆我们要反着来。虽然正着来也可以解决单纯的topK问题但是这一题是有add操作的如果正着来。那么前面pop掉最大的数据就丢失了。而最小的数据却没有关系因为小堆存的是最大的K个数。堆顶是最大K个数中最小的一个。 所以这一题我们可以建一个小堆。然后把nums所有的数push进去最后再把堆pop到K的大小。而每次add就push一次再pop一次即可维持堆的大小为K。
代码
class KthLargest {
public:priority_queueint,vectorint,greaterint _min_heap;int _k;KthLargest(int k, vectorint nums) {_k k ;for(auto n : nums)_min_heap.push(n); while(_min_heap.size() k) _min_heap.pop();}int add(int val) {_min_heap.push(val);if(_min_heap.size() _k) _min_heap.pop();return _min_heap.top();}
};运行结果 692. 前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] 10words[i] 由小写英文字母组成。k 的取值范围是 [1, **不同** words[i] 的数量]
**进阶**尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。
解题思路
首先这一题有2个关键点第一点是按频次比较。第二点是频次相同时按字母序排序。所以这里我们要一个哈希表来统治所有字符串出现的次数。然后再把哈希表的这一对keyvalue值入堆而堆的大小也和上题一样设置为K个。因为频次取前K个所以我们对频次用小根堆排。但是频次相同的字符串又要按字母序排所以对字母序排序我们又要用大堆。
比如第一个用例。我们用堆排好序是这样的。频次用小根堆排而频次相同我们则按大根堆对string排。 而因为我们的K为2所以堆的大小只能是2。最后变成这样。 而此时我TOP得到的是字母序较大的值所以我们在把堆的值填入返回的string数组时需要倒着填因为小的要放在前面。
要实现这种排序我们需要自己写一个cmp函数作为priority_queue的第三个模板参数。
代码
class Solution {typedef pairstring,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:vectorstring topKFrequent(vectorstring words, int k) {unordered_mapstring,int map; //1.统计所有字符出现次数for(auto word : words) map[word]; //2.将哈希表所有元素入堆priority_queuePSI,vectorPSI,cmp heap; for(auto it : map) heap.push({it.first,it.second}); //堆的大小只能为k while(heap.size() k) heap.pop(); //将堆的元素逆序放到ret数组中vectorstring ret(k); for(int i k - 1; i 0 ; i--){//将堆顶字符串放在数组的尾部逆序放ret[i] heap.top().first;heap.pop();}return ret;}
};运行结果 295. 数据流的中位数
题目链接[295. 数据流的中位数 题目描述
中位数是有序整数列表中的中间值。如果列表的大小是偶数则没有中间值中位数是两个中间值的平均值。
例如 arr [2,3,4] 的中位数是 3 。例如 arr [2,3] 的中位数是 (2 3) / 2 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。void addNum(int num) 将数据流中的整数 num 添加到数据结构中。double 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提示:
-105 num 105在调用 findMedian 之前数据结构中至少有一个元素最多 5 * 104 次调用 addNum 和 findMedian
解题思路
题目是找中位数那么我们可以用2个堆。一个大堆一个小端。大于中位数的值放小堆里面小于等于中位数的值放大堆里面。我们只需要保证两个堆的大小相等或者大堆的大小比小堆大1。每当一次add操作时我们先判断两个堆大小是否相等。如果相等则说明要往大堆push数据那么我们先把num放进小堆再取小堆的堆顶放入大堆这样大堆的长度就1了。如果不相等说明大堆的大小比小堆大1那么我们要往小堆push数据所以我们先把num放进大堆再取大堆的堆顶放入小堆。 代码
class MedianFinder {
public:priority_queueint,vectorint,greaterint _less_heap;//小堆priority_queueint,vectorint,lessint _greater_heap;//大堆MedianFinder() {}void addNum(int num) {if(_greater_heap.size() 0){//第一次插入直接入大堆_greater_heap.push(num); return; }//其他次插入判断俩个堆的大小if(_greater_heap.size() _less_heap.size()){//两个堆的大小相等则放进大堆不过需要先把num放进小堆取小堆的堆顶放入大堆_less_heap.push(num);int top _less_heap.top();_less_heap.pop();_greater_heap.push(top); }else {//两个堆大小不相等则说明大堆多一个把num放进大堆取大堆的堆顶放入小堆俩个堆的大小则平衡_greater_heap.push(num); int top _greater_heap.top();_greater_heap.pop();_less_heap.push(top);}}double findMedian() {//如果俩个堆大小相等返回堆顶和 /2 反之返回大堆堆顶if(_less_heap.size() _greater_heap.size())return (_less_heap.top() _greater_heap.top()) / 2.0; return _greater_heap.top();}
};
运行结果
