洛阳app开发公司_上海网站改版方案_关键词查询的分析网站_360搜索引擎首页

目录

1.1最后一块石头的重量

1.2数据流中的第K大元素

1.3前K个高频单词

1.4数据流的中位数

---

 

1.1最后一块石头的重量

1046. 最后一块石头的重量 - 力扣（LeetCode）

class Solution {
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int>mp;for(auto x:stones)mp.push(x);while(mp.size()>=2){int t1=mp.top();mp.pop();int t2=mp.top();mp.pop();if(t1!=t2){t1-=t2;mp.push(t1);}}if(mp.size()==1)return mp.top();else return 0;}
};

1.2数据流中的第K大元素

703. 数据流中的第 K 大元素 - 力扣（LeetCode）

topk问题

class KthLargest {
public:KthLargest(int k, vector<int>& nums) {_k=k;for(auto x:nums){mp.push(x);if(mp.size()>_k)mp.pop();}}int add(int val) {mp.push(val);if(mp.size()>_k)mp.pop();return mp.top();}int _k=0;priority_queue<int, vector<int>, greater<int>> mp;
};/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj = new KthLargest(k, nums);* int param_1 = obj->add(val);*/

1.3前K个高频单词

692. 前K个高频单词 - 力扣（LeetCode）

topk问题

class Solution {
public:struct kp{bool operator()(pair<string,int>&a,pair<string,int>&b){if(a.second==b.second)return a.first>b.first;else return a.second<b.second;}};vector<string> topKFrequent(vector<string>& words, int k) {priority_queue<pair<string,int>,vector<pair<string,int>>,kp>mp;map<string,int>hash;for(auto &x:words){hash[x]++;}for(auto &x:hash){mp.push(x);}vector<string>ans;while(k--){ans.push_back(mp.top().first);mp.pop();}return ans;}
};

1.4数据流的中位数

295. 数据流的中位数 - 力扣（LeetCode）

思路有3种：

1：数组放数据，每次add进去都要进行一次快排排序，find利用下标直接给出答案。但这个思路复杂度很高，每次add都是一个nlogn级别的操作，虽然find只要O1。但该题数据量很大

2.跟第一个很像，只是这里是利用插入排序，因为已有的数组必是有序，所以只需要对新的数在数组找合适的位置插入即可，所以只是插入排序的一次操作，复杂度就不会是on^2，而是n。但是这样还是很可能超时

3.利用大小堆。将这些数分别放在两个堆中，假设一个有序的数组，那么大堆存数组左半部分，小堆存数组右半部分，这样每次的插入操作都是logn的操作。然后让大堆的元素个数>=小堆元素个数，这样find的时候，如果当前元素总数是偶数，那么取两个堆的堆顶元素即可，如果是奇数，直接取大堆的堆顶元素即可。

class MedianFinder {
public:MedianFinder() {minority=new priority_queue<int>();majarity=new priority_queue<int,vector<int>,greater<int>>();_size=0;}void addNum(int num) {if(majarity->size()>0&&majarity->top()<num){int tmp=num;num=majarity->top();majarity->pop();majarity->push(tmp);}else if(minority->size()>0&&minority->top()>num){int tmp=num;num=minority->top();minority->pop();minority->push(tmp);}//这样操作是为了保持，num是>=大堆堆顶元素且小于小堆堆顶元素//这样后面无脑放就可以了，否则会使两个堆的关系出错（比如大堆堆顶元素大于小堆堆顶元素）if(minority->size()>majarity->size()){majarity->push(num);}else{minority->push(num);}_size++;}double findMedian() {if(_size%2==0){cout<<minority->top()<<" "<<majarity->top()<<endl;return (minority->top()+majarity->top())/2.0;}else{cout<<minority->top()<<endl;return minority->top();}return 0;}priority_queue<int>*minority;priority_queue<int,vector<int>,greater<int>>*majarity;int _size;
};