静安做网站,分销商家,怎样自己创造网站,济宁医院网站建设优先级队列 1.最后一块石头的重量2.数据流中的第 K 大元素4.前K个高频单词4.数据流的中位数 点赞#x1f44d;#x1f44d;收藏#x1f31f;#x1f31f;关注#x1f496;#x1f496; 你的支持是对我最大的鼓励#xff0c;我们一起努力吧!#x1f603;#x1f603; 1… 优先级队列 1.最后一块石头的重量2.数据流中的第 K 大元素4.前K个高频单词4.数据流的中位数 点赞收藏关注 你的支持是对我最大的鼓励我们一起努力吧! 1.最后一块石头的重量
题目链接1046. 最后一块石头的重量
题目分析 每一回合从中选出两块 最重的 石头x y那么两块石头都会被完全粉碎如果 x ! y那么重量较小的 x 石头将会完全粉碎而重量较大的 y 的石头新重量为 y-x。最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下就返回 0。 算法原理
每次挑选的是先挑一堆数中最大的那个数然后再挑一个剩下数中最大的数。这不正好符合大根堆的数据结构吗。
解法用堆来模拟这个过程
先拿数组的数创建一个大根堆每次从堆里面选择最大和次大两个数如果相等就是0不用加入到大根堆里如果不相等用最大的数减去次大的数把结果加入到堆里面。如果最后堆里还剩下一个数返回这个数。如果堆为空说明石头全都粉碎了返回0即可。
class Solution {
public:int lastStoneWeight(vectorint stones) {//1.拿元素创建一个大根堆priority_queueint heap(stones.begin(),stones.end());//2.模拟这个过程while(heap.size() 2){int s1 heap.top();heap.pop();int s2 heap.top();heap.pop();if(s1 ! s2) heap.push(s1 - s2);}return heap.size() ? heap.top() : 0;}
};2.数据流中的第 K 大元素
题目链接703. 数据流中的第 K 大元素
题目分析 设计一个找到数据流中第 k 大元素的类class。注意是排序后的第 k 大元素不是第 k 个不同的元素。 int add(int val) 将 val 插入数据流 nums 后返回当前数据流中第 k 大的元素。 算法原理
这道题其实考察的是一个非常经典的问题 TopK问题。 关于TopK问题有两种解题思路一种是堆一种是前面刚学的快速选择算法。快速选择排序虽然快但是对于海量的数据内存根本放不下。所以在海量数据情况最优的还是堆。 解法用 堆 来解决
创建一个大小为 k 的堆大根堆 or 小根堆循环 1.依次进堆 2.判断堆的大小是否超过 K
在堆的实现画图和代码分析建堆堆排序时间复杂度以及TOP-K问题对于求第K个最大元素我们也是将前K个数建个小堆然后将剩下的N-K个元素和堆顶元素做比较如果大于堆顶元素就先把栈顶元素pop掉也就是把堆中最小元素删除然后将它放进去。这样一直循环直到所有元素都比较完成。因为是一直把堆中最小的pop掉那堆的元素就是N个元素中最大的而堆顶就是第K个最大的元素别忘记我们这是一个小堆
这里我们也是建小堆依次进堆当堆大小超过K个pop堆顶元素把堆中最小元素pop掉并且使堆保持K个大小。每次都是堆中最小元素去掉。那最后堆中剩下的就是前K个最大元素而堆顶就是第K个最大元素。
考虑一下下面两个问题
用大根堆还是小根堆为什么要用大根堆小根堆
class KthLargest {
public:priority_queueint,vectorint,greaterint heap;int _k;KthLargest(int k, vectorint 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();}
};4.前K个高频单词
题目链接692. 前K个高频单词
题目分析 这是一个TopK的问题注意返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率 按字典顺序(由低向高) 排序。
算法原理
解法利用 “堆” 来解决 TopK 问题 预处理一下原始的字符串数组 用一个哈希表统计一下每一个单词出现的频次。 创建一个大小为 k 的堆类提供的比较函数满足不了要求我们要自己定义一个返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率 按字典顺序(由低向高) 排序。如果比较频次创建一个小根堆如果比较字典序(频次相同的时候)创建一个大根堆。所以说创建堆写比较函数的时候必须要考虑这两点当频次相同的时候字典序按照大根堆方式比较当频次不同的时候按照小根堆方式比较。 循环 1.依次进堆 2.判断堆的大小是否超过 K 提取结果
因为求前K大所以建的是一个小根堆然后提取堆顶元素在pop是一个升序的。有两种方式拿最终答案要么逆序一下取前K个要么从后往前取K个。
class Solution {
public:struct Compare{bool operator()(const pairstring,int l,const pairstring,int r){//频次不同按照小根堆比较, 频次相同字典序按照大根堆方式比较return l.second r.second || (l.second r.second l.first r.first);}};vectorstring topKFrequent(vectorstring words, int k) {vectorstring ret;// 1.统计一下每一个单词的频次mapstring,int count;for(auto str : words){count[str];}// 2.创建一个大小为 k 的小堆priority_queuepairstring,int,vectorpairstring,int,Compare heap;// 3.TopK 的主逻辑for(auto m : count){heap.push(m);if(heap.size() k) heap.pop();}// 4.提取结果vectorstring tmp;while(!heap.empty()){tmp.push_back(heap.top().first);heap.pop();}reverse(tmp.begin(),tmp.end());for(int i 0; i k; i)ret.push_back(tmp[i]);return ret;}
};4.数据流的中位数
题目链接295. 数据流的中位数
题目分析 给一个数据流让返回每次当前已经加入到数组的数据流的中位数。中位数是有序整数列表中的中间值。如果列表的大小是偶数则没有中间值中位数是两个中间值的平均值。表的大小是奇数直接返回中间的数。 算法原理
解法一直接sort
每次从数据流中来一个数插入数组中之后都对当前数组进行sort然后通过下标的方式找到中间数。 每次add加入一个数都要sort时间复杂度是O(nlogn)。总体时间复杂度是非常恐怖的。因为是下标访问find 时间复杂度是 O(1)
解法二插入排序的思想
[0,end] 有序插入 end 1使 [0, end 1]有序。这道题正好就是这样的思想。 add函数每次插入一个数的时候都需要从后往前扫描找一个插入的位置因此时间复杂度是O(n)find 也是通过下标去找 时间复杂度是O(1)
解法三大小堆来维护数据流的中位数
此时有一个数轴已经按照从小到大的排好序了这个时候想找中间数的时候。把这些数的前半部分放到一个大根堆里面后半部分放到小根堆里面。此时找中间值也很快前面较小的数放到大根堆里面堆顶元素是数轴中这些较小元素种最右边的值。后面较大的数放到小根堆里面堆顶元素是数轴中这些较大元素最左边。此时我们仅需根据数组中的元素的个数就可以求出中位数是多少了。如果数组是偶数个大根堆和小根堆正好把数轴平分然后大堆堆顶元素和小堆堆顶元素相加/2就是这个数组的中位数。如果数组是奇数个。我们就先人为规定一下数轴左边元素是m个右边是n个要么 m n要么 m n n n 1。如果 m n 正好平均分。如果数轴个数是奇数个人为规定左边大根堆多方一个元素m n(n n 1)此时中位数就是左边大根堆的堆顶元素。 向这样用大根堆存左边较小部分小根堆存右边较大部分。find 时间复杂度也是O(1)而add快了很多因为我们是从堆存这些元素的插入和删除每次调整堆仅需O(logn)
细节问题
add如何实现 假设现在有两个堆了。一个大根堆left一个小根堆right。left元素个数m个right元素个数n个left堆顶元素xright堆定元素y。如果此时来了一个数numnum要么放在left里要么放在right里。但是放好之后可能会破坏之前的规则
m nm n — m n 1
我们必须维护上面的规则才能正确找到数组中位数。 接下来分情况讨论
m n
num要么插入left要么插入right。
如果num要进入left那么num x但是别忘记 m n 有可能两个堆全为空num也是直接进入left。此时 m 比 n 多了一个。没关系直接进就行。
如果num进入right那条件是 num x。此时就有问题了。n m了而 n m是不被允许的所以我们要把右边堆调整一下就是拿right堆顶元素放到left里。因为right是一个小根堆堆顶就是最小值。拿到left还是能保证left堆里元素是较小的right堆里元素是较大的。拿right堆顶元素放到left里正好满足 m n 1。这里有一个细节问题必须num先进right堆然后再拿right堆定元素放到left因为 x num y如果直接把y拿过去了就破坏了left都是较小元素。right都是较大元素。 m n — m n 1
如果num进入left那么num x 但是此时不满足 m n 1因此 进栈后将栈顶元素给right。
如果num进入right那么num x , m n了直接进就行了 class MedianFinder {
public:MedianFinder() {}void addNum(int num) {// 分类讨论即可int m left.size(), n right.size();if(m n) // 左右两个堆的元素个数相同{if(m 0 || num left.top())left.push(num);else{right.push(num);left.push(right.top());right.pop();}}else //左边堆的元素个数比右边堆元素个数多 1{if(num left.top()){left.push(num);right.push(left.top());left.pop();}elseright.push(num);}}double findMedian() {int m left.size(), n right.size();if(m n) return (left.top() right.top()) / 2.0;else return left.top();}private: priority_queueint left;priority_queueint,vectorint,greaterint right;
};
