当前位置: 首页 > news >正文

day13 滑动窗口最大值 前K个高频元素

题目1:239  滑动窗口最大值

题目链接:239 滑动窗口最大值

题意

长度为K的滑动窗口从整数数组的最左侧移动到最右侧,每次只移动1位,求滑动窗口中的最大值

不能使用优先级队列,如果使用大顶堆,最终要pop的元素不知道是哪一个,因为大顶堆已经对队列中的元素进行排序了,元素的顺序发生了改变

暴力解法

对窗口内的所有元素进行排序

单调队列

由于窗口每次只移动1步,所以每真正push一次,就收集一次最大值即可,最大值放到队列的出口

队列只维护窗口中的最大值即可,且队列里的元素是从左到右依次递减的

pop():若滑动窗口原本要移除的元素(val)就是单调队列的出口(front)元素(滑动窗口的最大值),那么就弹出元素

push():如果要放入的元素(val)大于入口(back)的元素,就将入口处(back)小于val的元素逐个卷走,元素再在入口处(back)处入栈

getmaxvalue():每次移动窗口时,队列出口处(front())的元素即为当前窗口的最大值

伪代码

逻辑
例1:前一个滑动窗口删除的元素会不会影响后一个滑动窗口?

代码

class Solution {  
private:class MyQueue{public:deque<int> que;//双向队列void pop(int val){if(!que.empty()&&que.front()==val){que.pop_front();}}void push(int val){//去掉入口处比其小的元素while(!que.empty()&&que.back()<val){que.pop_back();}que.push_back(val);}int getmaxvalue(){return que.front();}};    
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> result;for(int i=0;i<k;i++){que.push(nums[i]);}//第一个滑动窗口的元素result.push_back(que.getmaxvalue());for(int i=k;i<nums.size();i++){//先弹出元素,因为窗口的大小是一定的,只能先弹出元素,再放入元素que.pop(nums[i-k]);//再放入元素que.push(nums[i]);//求最大值result.push_back(que.getmaxvalue());}return result;}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(k)

题目2:347  前K个高频元素

题目链接:347 前K个高频元素

题意

返回整数数组nums中出现频率前k高的元素

暴力解法

使用map数组,元素是key,频率是value,然后将value从大到小排序,输出前k个元素(所有元素进行排序)

优先级队列(小顶堆)

为了优化时间复杂度,可以只维护k个元素,没有必要排序所有元素,想到使用优先级队列。

大顶堆,小顶堆擅长求解在大数据集内求排名靠前的元素,堆的底层实现是二叉树

那么使用大顶堆还是使用小顶堆呢?

如果使用大顶堆,那么加入该元素时,弹出最大值,不符题意

如果使用小顶堆,那么加入该元素时,弹出最小值,符合题意,所以,使用小顶堆

使用优先级队列实现大顶堆的话,cmopare函数从大到小排,实现小顶堆的话,compare函数从小到大排

伪代码

代码

class Solution {
public:class mycomparision{public:bool operator()(const pair<int,int>& kv1,const pair<int,int>& kv2){return kv1.second > kv2.second;}};//定义一个类之后,一定要添加;vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> map;//统计元素出现的频率for(int i=0;i<nums.size();i++){map[nums[i]]++;}//使用优先级队列定义小顶堆priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparision> que;//pair<int,int>表示键值对的数据类型<元素(int),频率(int)>//vector<pair<int,int>>表示vector作为que的底层容器,存储元素//遍历map中的元素,小顶堆只维护前k个高频元素for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){que.push(*it);//*it代表迭代器it指向的key-value键值对if(que.size()>k){que.pop();//弹出当前小顶堆中的最小值}}//将小顶堆中频率排名前k的key元素按照频率从高到低放到数组中vector<int> result(k);//这里一定要定义result的大小,因为后续是对result的下标位置进行操作for(int i=k-1;i>=0;i--){result[i] = que.top().first;que.pop();}return result;}
};
  • 时间复杂度: O(nlogk)
  • 空间复杂度: O(n)
逻辑
例1:最后将堆中的元素放入到数组中时,如果写出这样
vector<int> result;

会报如下错误

原因就是还未给result数组分配内存空间,所以访问result[i]时出错,相当于访问了一个空的空间,和访问空指针差不多一个意思。

相关文章:

day13 滑动窗口最大值 前K个高频元素

题目1&#xff1a;239 滑动窗口最大值 题目链接&#xff1a;239 滑动窗口最大值 题意 长度为K的滑动窗口从整数数组的最左侧移动到最右侧&#xff0c;每次只移动1位&#xff0c;求滑动窗口中的最大值 不能使用优先级队列&#xff0c;如果使用大顶堆&#xff0c;最终要pop的…...

Unity——VContainer的依赖注入

一、IOC控制反转和DI依赖倒置 1、IOC框架核心原理是依赖倒置原则 C#设计模式的六大原则 使用这种思想方式&#xff0c;可以让我们无需关心对象的生成方式&#xff0c;只需要告诉容器我需要的对象即可&#xff0c;而告诉容器我需要对象的方式就叫做DI&#xff08;依赖注入&…...

【面试突击】Spring 面试实战

&#x1f308;&#x1f308;&#x1f308;&#x1f308;&#x1f308;&#x1f308;&#x1f308;&#x1f308; 欢迎关注公众号&#xff08;通过文章导读关注&#xff1a;【11来了】&#xff09;&#xff0c;及时收到 AI 前沿项目工具及新技术 的推送 发送 资料 可领取 深入理…...

【Linux】Ubuntu 22.04 上安装最新版 Nextcloud Hub 7 (28.0.1)

在 Ubuntu 22.04 上安装 PHP 版本 安装多个 PHP 版本的最简单方法是使用来自 Debian 开发人员 Ondřej Sur 的 PPA。要添加此 PPA,请在终端中运行以下命令。如果要从 PPA 安装软件,则需要 software-properties-common 包。它会自动安装在 Ubuntu 桌面上,但可能会在您的 Ubuntu…...

PHP项目如何自动化测试

开发和测试 测试和开发具有同等重要的作用 从一开始&#xff0c;测试和开发就是相向而行的。测试是开发团队的一支独立的、重要的支柱力量。 测试要具备独立性 独立分析业务需求&#xff0c;独立配置测试环境&#xff0c;独立编写测试脚本&#xff0c;独立开发测试工具。没有…...

WEB 3D技术 three.js 3D贺卡(1) 搭建基本项目环境

好 今天 我也是在网上学的 带着大家一起来做个3D贺卡 首先 我们要创建一个vue3的项目、 先创建一个文件夹 装我们的项目 终端执行 vue create 项目名称 例如 我的名字想叫 greetingCards 就是 vue create greetingcards因为这个名录 里面是全部都小写的 然后 下面选择 vue3 …...

短视频IP运营流程架构SOP模板PPT

【干货资料持续更新&#xff0c;以防走丢】 短视频IP运营流程架构SOP模板PPT 部分资料预览 资料部分是网络整理&#xff0c;仅供学习参考。 抖音运营资料合集&#xff08;完整资料包含以下内容&#xff09; 目录 抖音15秒短视频剧本创作公式 在抖音这个短视频平台上&#…...

python爬虫之线程与多进程知识点记录

一、线程 1、概念 线程 在一个进程的内部&#xff0c;要同时干多件事&#xff0c;就需要同时运行多个“子任务”&#xff0c;我们把进程内的这些“子任务”叫做线程 是操作系统能够进行运算调度的最小单位。它被包含在进程之中&#xff0c;是进程中的实际运作单位。一条线程指…...

基于Java (spring-boot)的停车场管理系统

一、项目介绍 基于Java (spring-boot)的停车场管理系统、预订车位系统、停车缴费系统功能&#xff1a; 登录、注册、后台首页、用户信息管理、车辆信息管理、新增车辆、车位费用设置、停泊车辆查询、车辆进出管理、登录日志查询、个人中心、预定停车位、缴费信息。 适用人群&…...

微软Office 2019 批量授权版

软件介绍 微软办公软件套件Microsoft Office 2019 专业增强版2024年1月批量许可版更新推送&#xff01;Office2019正式版2018年10月份推出&#xff0c;主要为多人跨平台办公与团队协作打造。Office2019整合对过去三年在Office365里所有功能&#xff0c;包括对Word、Excel、Pow…...

ChatGLM2-6B 大语言模型本地搭建

ChatGLM模型介绍&#xff1a; ChatGLM2-6B 是清华 NLP 团队于不久前发布的中英双语对话模型&#xff0c;它具备了强大的问答和对话功能。拥有最大32K上下文&#xff0c;并且在授权后可免费商用&#xff01; ChatGLM2-6B的6B代表了训练参数量为60亿&#xff0c;同时运用了模型…...

WindowsServer安装mysql最新版

安装 下载相应mysql安装包&#xff1a; MySQL :: Download MySQL Installer 选择不登陆下载 双击运行下载好的mysql-installer-community-*.*.*.msi 进入类型选择页面&#xff0c;本人需要mysql云服务就选择了server only server only&#xff08;服务器&#xff09;&#x…...

gin切片表单验证

在Gin中对切片进行表单验证的步骤与对其他类型的字段进行验证类似。以下是一些基本步骤&#xff0c;我们可以根据具体的需求进行调整&#xff1a; 定义结构体&#xff1a; 创建一个结构体&#xff0c;用于存储表单数据。确保结构体中的字段类型与你预期的表单数据类型一致。 使…...

openssl3.2 - 官方demo学习 - certs

文章目录 openssl3.2 - 官方demo学习 - certs概述笔记官方的实验流程mkcerts.sh - 整理ocsprun.sh - 整理ocspquery.sh - 整理从mkcerts.sh整理出来的27个.bata1_create_certificate_directly.cmda2_Intermediate_CA_request_first.cmda3_Sign_request_CA_extensions.cmda4_Ser…...

Datawhale 大模型基础理论 Day1 引言

开源链接如下&#xff1a;https://github.com/datawhalechina/so-large-lm/blob/main/docs/content/ch01.md 语言模型的概念&#xff1a;即能够赋予每个有意义的词&#xff08;token&#xff09;以一定的概率的一个函数的集合。 语言模型可以被用来评估输入的质量&#xff0c…...

HarmonyOS应用开发学习笔记 UIAbility组件与UI的数据同步 EventHub、globalThis

1、 HarmoryOS Ability页面的生命周期 2、 Component自定义组件 3、HarmonyOS 应用开发学习笔记 ets组件生命周期 4、HarmonyOS 应用开发学习笔记 ets组件样式定义 Styles装饰器&#xff1a;定义组件重用样式 Extend装饰器&#xff1a;定义扩展组件样式 5、HarmonyOS 应用开发…...

leetcode每日一题44

130. 被围绕的区域 图论 dfs/bfs dfs代码框架 void dfs(参数) {if (终止条件) {存放结果;return;}for (选择&#xff1a;本节点所连接的其他节点) {处理节点;dfs(图&#xff0c;选择的节点); // 递归回溯&#xff0c;撤销处理结果} }思路&#xff1a;本题要求找到被x围绕的陆…...

idea写sql语句快捷键提醒,mapper注解开发,mybatis

第一步&#xff1a;注入SQL语言 1.显示上下文操作&#xff08;没有这个选项的话就选中sql然后直接alt回车快捷键&#xff09;2.注入语言或引用 3.mysql 第二步&#xff1a;配置MySQL数据库连接 1.首先点击侧边的数据库&#xff0c;再点击上面的加号 2.点击数据源&#xff…...

002 Golang-channel-practice

第二题&#xff1a; 创建一个生产器和接收器&#xff0c;再建立一个无缓冲的channel。生产器负责把数据放进管道里&#xff0c;接收器负责把管道里面的数据打印出来。这里我们开5个协程把数据打印出来。 直接上代码&#xff01; package mainimport ("fmt" )func …...

MFC为对话框资源添加类

VC6新建一个对话框类型的工程; 建立之后资源中默认有2个对话框,一个是主对话框,About这个是默认建立的关于版权信息的; 然后主对话框有对应的.h和.cpp文件;可以在其中进行编程; 默认建立的有一个 关于 对话框; 在资源中新插入一个对话框,IDD_DIALOG1是对话框ID; 新加…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...