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

做网站外包公司名称大全/免费开发网站

做网站外包公司名称大全,免费开发网站,贤邦网站建设app开发,漳浦网站建设文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目 标题和出处 标题:数组的度 出处:697. 数组的度 难度 4 级 题目描述 要求 给定一个非空且只包含非负数的整数数组 nums\texttt{nums}nums,数组的…

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
  • 解法
    • 思路和算法
    • 代码
    • 复杂度分析

题目

标题和出处

标题:数组的度

出处:697. 数组的度

难度

4 级

题目描述

要求

给定一个非空且只包含非负数的整数数组 nums\texttt{nums}nums,数组的的定义是指数组中任一元素出现频数的最大值。

你的任务是在 nums\texttt{nums}nums 中找到与 nums\texttt{nums}nums 拥有相同大小的度的最短(连续)子数组的长度。

示例

示例 1:

输入:nums=[1,2,2,3,1]\texttt{nums = [1,2,2,3,1]}nums = [1,2,2,3,1]
输出:2\texttt{2}2
解释:
输入数组的度是 2\texttt{2}2,因为元素 1\texttt{1}12\texttt{2}2 都出现 2\texttt{2}2 次。
度相同的子数组如下:
[1,2,2,3,1],[1,2,2,3],[2,2,3,1],[1,2,2],[2,2,3],[2,2]\texttt{[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]}[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短的长度为 2\texttt{2}2,所以返回 2\texttt{2}2

示例 2:

输入:nums=[1,2,2,3,1,4,2]\texttt{nums = [1,2,2,3,1,4,2]}nums = [1,2,2,3,1,4,2]
输出:6\texttt{6}6
解释:
数组的度是 3\texttt{3}3,因为元素 2\texttt{2}2 出现 3\texttt{3}3 次。
所以 [2,2,3,1,4,2]\texttt{[2,2,3,1,4,2]}[2,2,3,1,4,2] 是最短子数组,因此返回 6\texttt{6}6

数据范围

  • 1≤nums.length≤5×104\texttt{1} \le \texttt{nums.length} \le \texttt{5} \times \texttt{10}^\texttt{4}1nums.length5×104
  • 0≤nums[i]<5×104\texttt{0} \le \texttt{nums[i]} < \texttt{5} \times \texttt{10}^\texttt{4}0nums[i]<5×104

解法

思路和算法

由于数组的度为数组中任一元素出现频数的最大值,数组中的任一元素的出现频数都不会超过数组的度。在与数组 nums\textit{nums}nums 拥有相同大小度的子数组中,一定至少包含一个出现频数等于数组的度的元素,且该元素在该子数组中的出现频数等于该元素在数组 nums\textit{nums}nums 中的出现频数,即该子数组包含数组 nums\textit{nums}nums 中的全部该元素。

为了找到与数组 nums\textit{nums}nums 拥有相同大小度的最短子数组的长度,需要记录每个元素在数组 nums\textit{nums}nums 中的出现频数,以及每个元素在数组 nums\textit{nums}nums 中的下标范围(即该元素第一次出现的下标和最后一次出现的下标)。使用两个哈希表分别记录出现频数和下标范围。

遍历数组 nums\textit{nums}nums,对于每个元素,分别更新两个哈希表,同时维护数组的度,如果当前元素的出现频数大于数组的度则将数组的度更新为当前元素的出现频数。遍历结束时,即可得到每个元素的出现频数和下标范围,以及数组的度。

由于数组 nums\textit{nums}nums 满足与其本身拥有相同大小的度,因此将最短子数组的长度初始化为数组 nums\textit{nums}nums 的长度。遍历哈希表中的每个元素,如果一个元素的出现频数等于数组的度,则根据该元素的下标范围计算包含全部该元素的最短子数组的长度(长度计算方法为该元素的最后一次出现的下标和第一次出现的下标之差加 111),并更新最短子数组的长度。遍历结束之后即可得到与数组 nums\textit{nums}nums 拥有相同大小度的最短子数组的长度。

也可以使用一个哈希表同时记录每个元素的出现频数和下标范围,和使用两个哈希表的做法是等价的。

代码

class Solution {public int findShortestSubArray(int[] nums) {int degree = 0;Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();Map<Integer, int[]> rangeMap = new HashMap<Integer, int[]>();int length = nums.length;for (int i = 0; i < length; i++) {int num = nums[i];int frequency = frequencyMap.getOrDefault(num, 0) + 1;frequencyMap.put(num, frequency);degree = Math.max(degree, frequency);if (!rangeMap.containsKey(num)) {rangeMap.put(num, new int[]{i, i});} else {rangeMap.get(num)[1] = i;}}int minLength = length;Set<Integer> set = frequencyMap.keySet();for (int num : set) {if (frequencyMap.get(num) == degree) {int[] range = rangeMap.get(num);minLength = Math.min(minLength, range[1] - range[0] + 1);}}return minLength;}
}

复杂度分析

  • 时间复杂度:O(n)O(n)O(n),其中 nnn 是数组 nums\textit{nums}nums 的长度。需要遍历数组一次,使用两个哈希表分别记录每个元素出现频数和下标范围,然后遍历两个哈希表计算最短子数组的长度,由于哈希表中的元素个数不超过数组长度,因此时间复杂度是 O(n)O(n)O(n)

  • 空间复杂度:O(n)O(n)O(n),其中 nnn 是数组 nums\textit{nums}nums 的长度。需要使用两个哈希表分别记录每个元素出现频数和下标范围,两个哈希表中的元素个数都不会超过 nnn

相关文章:

哈希表题目:数组的度

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目 标题和出处 标题&#xff1a;数组的度 出处&#xff1a;697. 数组的度 难度 4 级 题目描述 要求 给定一个非空且只包含非负数的整数数组 nums\texttt{nums}nums&#xff0c;数组的…...

初识rollup 打包、配置vue脚手架

rollup javascript 代码打包器&#xff0c;它使用了 es6 新标准代码模块格式。 特点&#xff1a; 面向未来&#xff0c;拥抱 es 新标准&#xff0c;支持标准化模块导入、导出等新语法。tree shaking 静态分析导入的代码。排除未实际引用的内容兼容现有的 commonJS 模块&#…...

软考网络工程师证书有用吗?

当然有用&#xff0c;但是拿到网络工程师证书的前提是对你自己今后的职业发展有帮助&#xff0c;用得到才能对你而言发挥它最大的好处。软考证书的具体用处&#xff1a;1.纳入我国高校人才培养和教学体系目前&#xff0c;软考已经被纳入高校人才培养和教学体系。在很多高校中&a…...

postgresql 自动备份 bat实现

postgres数据据备分,用cmd命令有些烦,写了个bat实现 BAT脚本中常用的注释命令有rem、@rem和:: rem、@rem和::用法都很简单,直接在命令后加上要注释的语句即可。例如下图,语言前加了rem,运行BAT时就会自动忽略这个句子。需要注释多行时,每行前面都要加上rem、@rem和::。…...

gdb:在命令行中会莫名暂停;detach-on-fork

这个没有捕获到断点的原因是,可能是多线程的问题,需要设置: set detach-on-fork off On Linux, if you want to debug both the parent and child processes, use the command: set detach-on-fork on/off on 默认设置,gdb会放弃子线程(或者父线程,受follow-fork-mode的…...

【3.9】RedisAOF日志、字符串、操作系统进程管理

4. 进程管理 进程、线程基础知识 什么是进程 我们编写的代码只是一个存储在硬盘的静态文件&#xff0c;通过编译后就会生成二进制可执行文件&#xff0c;当我们运行这个可执行文件后&#xff0c;它会被装载到内存中&#xff0c;接着 CPU 会执行程序中的每一条指令&#xff0c;…...

安装mayavi的成功步骤

这篇文章是python 3.6版本&#xff0c;windows系统下的安装&#xff0c;其他python版本应该也可以&#xff0c;下载对应的包即可。 一定不要直接pip install mayavi&#xff0c;这个玩意儿对vtk的版本有要求。 下载whl包 搞了很久不行&#xff0c;咱也别费那个劲了&#xff0…...

vue+echarts.js 实现中国地图——根据数值表示省份的深浅——技能提升

最近在写后台管理系统&#xff0c;遇到一个需求就是 中国地图根据数值 展示深浅颜色。 效果图如下&#xff1a; 直接上代码&#xff1a; 1.html部分 <div id"Map"></div>2.css部分——一定要设置尺寸 #Map {width: 100%;height: 400px; }3.js部分 …...

[oeasy]python0104_指示灯_显示_LED_辉光管_霓虹灯

编码进化 回忆上次内容 x86、arm、riscv等基础架构 都是二进制的包括各种数据、指令 但是我们接触到的东西 都是屏幕显示出来的字符 计算机 显示出来的 一个个具体的字型 计算机中用来展示的字型 究竟是 如何进化的 呢&#xff1f;&#x1f914;&#x1f914; 模拟电路时…...

Easy Deep Learning——卷积层

为什么需要卷积层&#xff0c;深度学习中的卷积是什么&#xff1f; 在介绍卷积之前&#xff0c;先引入一个场景 假设您在草地上漫步&#xff0c;手里拿着一个尺子&#xff0c;想要测量草地上某些物体的大小&#xff0c;比如一片叶子。但是叶子的形状各异&#xff0c;并且草地非…...

深入分析@Bean源码

文章目录一、源码时序图二、源码解析1. 运行案例程序启动类2. 解析AnnotationConfigApplicationContext类的AnnotationConfigApplicationContext(Class<?>... componentClasses)构造方法3. 解析AbstractApplicationContext类的refresh()方法4. 解析AbstractApplicationC…...

Web Components学习(1)

一、什么是web components 开发项目的时候为什么不手写原生 JS&#xff0c;而是要用现如今非常流行的前端框架&#xff0c;原因有很多&#xff0c;例如&#xff1a; 良好的生态数据驱动试图模块化组件化等 Web Components 就是为了解决“组件化”而诞生的&#xff0c;它是浏…...

Element-UI实现复杂table表格结构

Element-UI组件el-table用于展示多条结构类似的数据&#xff0c;可对数据进行排序、筛选、对比或其他自定义操作。将使用到以下两项&#xff0c;来完成今天demo演示&#xff1a;多级表头&#xff1a;数据结构比较复杂的时候&#xff0c;可使用多级表头来展现数据的层次关系。合…...

Azure AD 与 AWS 单一帐户SSO访问集成,超详细讲解,包括解决可能出现的错误问题

本教程介绍如何将 AWS Single-Account Access 与 Azure Active Directory (Azure AD) 相集成。 将 AWS Single-Account Access 与 Azure AD 集成后&#xff0c;可以&#xff1a; 在 Azure AD 中控制谁有权访问 AWS Single-Account Access。让用户使用其 Azure AD 帐户自动登录…...

lvgl 笔记 按钮部件 (lv_btn) 和 开关部件 (lv_switch)

按钮基础使用方法&#xff1a; lv_btn 和 lb_obj 使用方法一样&#xff0c;只是外表并不相同&#xff0c;基础创建方法只需一行代码。 lv_obj_t* btn lv_btn_create(lv_scr_act()); 添加大小和位置&#xff1a; lv_obj_t* btn lv_btn_create(lv_scr_act()); lv_obj_set_s…...

Python高频面试题——生成器(最通俗的讲解)

生成器定义在 Python 中&#xff0c;使用了 yield 的函数被称为生成器&#xff08;generator&#xff09;。跟普通函数不同的是&#xff0c;生成器是一个返回迭代器的函数&#xff0c;只能用于迭代操作&#xff0c;更简单点理解生成器就是一个迭代器。 在调用生成器运行的过程中…...

品牌软文怎么写?教你几招

软文是什么&#xff1f;软文的本质就是广告&#xff0c;当然不是明晃晃的推销&#xff0c;而是自然隐晦地植入产品信息&#xff0c;引导更多用户自愿下单。 品牌软文对于写手的经验、内容的质量要求都相对较高&#xff0c;否则写出来的软文无法达到预期的效果。品牌软文怎么写…...

Kubernetes (k8s) 污点(Taint)介绍、示例

Kubernetes (k8s) 污点&#xff08;Taint&#xff09; 是一种机制&#xff0c;用于标记一个节点&#xff08;Node&#xff09;不可被调度的状态。它可以将一个污点标记添加到节点上&#xff0c;以防止 Pod 被调度到该节点上。污点可以用于实现各种策略&#xff0c;例如分离故障…...

Docker学习(二十一)构建 java 项目基础镜像

目录1.下载 JDK 包2.编写 Dockerfile3.构建镜像4.创建容器测试1.下载 JDK 包 JDK各版本官网下载地址&#xff1a; https://www.oracle.com/java/technologies/downloads/archive/#JavaSE 这里我们以 JDK 8u351 为例&#xff0c;点击 Java SE (8U211 and later)。 点击下载 jd…...

python中的上下文原理

目录with语句上下文管理器原理自定义上下文管理器contextmanager 装饰器with语句 在我们日常使用场景中&#xff0c;经常会操作一些资源&#xff0c;比如文件对象、数据库连接、Socket连接等&#xff0c;资源操作完了之后&#xff0c;不管操作的成功与否&#xff0c;最重要的事…...

可复用测试用例描述要素

测试用例的输入、操作、预期结果和评估标准、前提条件是测试用例不可少的要素&#xff0c;但对于可复用测试用例而言&#xff0c;这是不够的。本文在文献规定的测试用例要素基础上&#xff0c;增加了新的内容。从而从多个角度完整地对可复用测试用例进行了描述&#xff0c;为可…...

lnmp中遇到open_basedir配置无效问题

在使用LNMP包安装PHP时&#xff0c;发现直接修改php.ini的配置是无法生效的&#xff0c;其原因竟然是因为nginx的配置文件&#xff0c;覆盖了php.ini的配置。 解决&#xff1a; 1、找到nginx的open_basedir配置文件&#xff1a;&#xff08;下面是我的文件地址&#xff09; …...

SpringBoot【知识加油站】---- REST开发

SpringBoot【知识加油站】---- REST开发1. REST 简介2. REST 风格3. RESTful 入门案例1. REST 简介 REST&#xff1a;Representaional State Transfer&#xff0c;表现形式状态转换 传统风格资源描述形式 http://localhost/user/getById?id1 http://localhost/user/saveUser…...

三 Go的语言容器

1. 数组 数组是一个由固定长度的特定类型元素组成的序列&#xff0c;一个数组可以由零个或多个元素组成。因为数组的长度是固定的&#xff0c;所以在Go语言中很少直接使用数组 声明语法&#xff1a; var 数组变量名 [元素数量]Typepackage main import ("fmt" ) fu…...

2023年全国最新会计专业技术资格精选真题及答案16

百分百题库提供会计专业技术资格考试试题、会计考试预测题、会计专业技术资格考试真题、会计证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 一、单选题 1.下列各项关于会计监督职能的表述中&#xff0c;正确的是&#xff…...

模板进阶(仿函数,特化等介绍)

非类型模板参数 模板参数有类型形参和非类型形参&#xff1b; 类型形参&#xff1a;使用typename或者class修饰的参数类型名称 非类型形参&#xff1a;一个普通常量作为模板参数形参&#xff0c;不能为浮点数&#xff0c;字符类型以及类对象&#xff1b; #include<iostrea…...

Beats:在 Docker 中同时部署 Metricbeat 和 Elasticsearch

在本教程中&#xff0c;我们将部署一个 metricbeat 来监控正在运行的容器的健康状况和系统指标。 为什么需要监控&#xff0c;为什么需要 Metricbeat&#xff1f; 一个常见的问题&#xff0c;但很少有人回答。 首先&#xff0c;无论我们部署的是 docker 容器还是老式的金属箱&…...

编码技巧——Redis Pipeline

本文介绍Redis pipeline相关的知识点及代码示例&#xff0c;包括Redis客户端-服务端的一次完整的网络请求、pipeline与client执行多命令的区别、pipeline与Redis"事务"、pipeline的使用代码示例&#xff1b; pipeline与client执行多命令的区别 Redis是一种基于客户…...

ArcGIS制图技巧:制图入门与点、线、面状符号制作

目的&#xff1a; 1、了解地图制作目的&#xff1b; 2、了解在ArcMap平台中制作地图大致过程。 3、掌握地形图生成的操作&#xff1b; 4、掌握地形图的正确输出方法。 5、理解点状符号、线状符号、面状符号的基本概念&#xff1b; 6、理解地形点状符号、线状符号、面状符…...

Java基础 关于字典数据维护接口设计

开发环境 Eclipse2022JDK1.8 目录 1. 概述 2. 实现步骤 2.1 定义通用接口 2.2 定义实体类 2.3 接口扩展 2.4 接口实现 2.5 功能测试 3. 结语 1. 概述 每一个信息系统或多或少都带有一些数据字典&#xff0c;在维护上&#xff0c;基本上分为增删改查&#xff0c;也就是对数据…...