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

哈希表题目:数组的度

文章目录

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

题目

标题和出处

标题:数组的度

出处: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;最重要的事…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

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

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

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...