Day12|239.滑动窗口最大值|347.前K个高频元素-创新互联
239. 滑动窗口大值
网站建设公司,为您提供网站建设,网站制作,网页设计及定制网站建设服务,专注于企业网站设计,高端网页制作,对成都阳台护栏等多个行业拥有丰富的网站建设经验的网站建设公司。专业网站设计,网站优化推广哪家好,专业网站推广优化,H5建站,响应式网站。注意点:
1.确定一个双头队列deque
2.将滑动窗口的大值放到deque的最前面--front函数;如果滑动窗口往右移动,删除的值将和queue的front进行比较,如果相同,则弹出--pop函数;滑动窗口右移,新增加的数字将与queue中的数字进行比较,采用单增序列进行排列,将小的全删除了
3.push_back()函数是链表(vector string deque)的成员函数,push() 函数是栈Stack的成员函数
class Solution {
private:
class MyQueue{
public:
dequeque;
// 每次弹出的时候和que队列出口元素进行对比,如果相同则弹出
void pop(int value) {
if(!que.empty() && value == que.front())
que.pop_front();
}
// 将value压入到队列中,value与队列中的元素比较,将值放到相应的位置,比value小的数值直接丢弃
void push(int value) {
while(!que.empty() && value >que.back())
que.pop_back();
que.push_back(value);
}
// 获得大值
int front(){
return que.front();
}
};
public:
vectormaxSlidingWindow(vector& nums, int k) {
MyQueue que;
vectorresult;
for(int i =0; i
347. 前 K 个高频元素
注意点:
1.优先队列需要三个参数,第一个参数是数据类型,第二个队列是数据容器,第三个是排序方式
//升序队列,头部是最小的元素,即小顶堆
priority_queue,greater>q;
//降序队列,头部是大的元素,即小顶堆
priority_queue,less>q;
2. >表示右边的大,是降序排列
3.采用小堆顶进行统计前k个元素的个数
4.因为小堆顶采用最小次数的元素出现在小堆顶的堆顶,在进行最后的输出的时候,进行倒序输出
class Solution {
public:
// 小堆顶
class mycomparision {
public:
bool operator()(const pair& lhs, const pair& rhs) {
return lhs.second >rhs.second;//>表示右边的大,是降序排列
}
};
vectortopKFrequent(vector& nums, int k) {
unordered_mapmap;//key是元素 value是出现的次数
for(int i = 0; i< nums.size(); i++) {
map[nums[i]]++;
}
// 优先队列需要三个参数,第一个参数是数据类型,第二个队列是数据容器,第三个是排序方式
priority_queue, vector>, mycomparision>pri_que;
for(auto it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);//it包含if(pri_que.size() >k)
pri_que.pop();
}
vectorresult(k);
for(int i = k-1; i>= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
文章题目:Day12|239.滑动窗口最大值|347.前K个高频元素-创新互联
网页地址:http://scyanting.com/article/dgiiss.html