算法每日一题: 使用循环数组所有元素相等的最少秒数 | 哈希

本文主要是介绍算法每日一题: 使用循环数组所有元素相等的最少秒数 | 哈希,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

大家好,我是星恒,今天给大家带来的是一道需要感觉规律的题目,只要读懂题目中的规律,就可以做出来了
这道题用到了哈希,还有一个关键点比较类似循环队列

题目:leetcode 2808

给你一个下标从 0 开始长度为 n 的数组 nums 。
每一秒,你可以对数组执行以下操作:

  • 对于范围在 [0, n - 1] 内的每一个下标 i ,将 nums[i] 替换成 nums[i] ,nums[(i - 1 + n) % n] 或者 nums[(i + 1) % n] 三者之一。

注意,所有元素会被同时替换。
请你返回将数组 nums 中所有元素变成相等元素所需要的 最少 秒数。

示例 1:

输入:nums = [1,2,1,2]
输出:1
解释:我们可以在 1 秒内将数组变成相等元素:
- 第 1 秒,将每个位置的元素分别变为 [nums[3],nums[1],nums[3],nums[3]] 。变化后,nums = [2,2,2,2] 。
1 秒是将数组变成相等元素所需要的最少秒数。

示例 2:

输入:nums = [2,1,3,3,2]
输出:2
解释:我们可以在 2 秒内将数组变成相等元素:
- 第 1 秒,将每个位置的元素分别变为 [nums[0],nums[2],nums[2],nums[2],nums[3]] 。变化后,nums = [2,3,3,3,3] 。
- 第 2 秒,将每个位置的元素分别变为 [nums[1],nums[1],nums[2],nums[3],nums[4]] 。变化后,nums = [3,3,3,3,3] 。
2 秒是将数组变成相等元素所需要的最少秒数。

示例 3:

输入:nums = [5,5,5,5]
输出:0
解释:不需要执行任何操作,因为一开始数组中的元素已经全部相等。

提示:

  • 1 <= n == nums.length <= 105
  • 1 <= nums[i] <= 109

分析:
阅读题目,大家首先可能对这两个式子有些迷惑:nums[(i - 1 + n) % n] 和 nums[(i + 1) % n]
其实他们就是处理了一下首尾元素:

  • nums[(i - 1 + n) % n]:当元素为首元素时(下标为0),式子变为了nums[n - 1];其他元素相当于nums[i - 1]
  • nums[(i + 1) % n]:当元素为尾元素时(下标为n - 1),式子变为了nums[0];其他元素相当于nums[i + 1]

这样做的目的是可以让首尾相连,感觉首元素和尾元素相邻了

好,知道了这个,我们正式开始分析这道题目:
读题,我们可以知道,一个元素,一次可以将相邻的两个元素下标变为自己的,所以每一秒我们可以影响相邻元素。


结合上面的理论,我们来看这个图

也就是说,变成相等元素所需要的 最少 秒数,就是两个相邻相同元素的 最大 距离 / 2
注意,首尾距离也要计算

至于我们选择哪个作为相同元素更好,我们只要将每一种元素的所需最大秒数求出来比较就可以了

我们来看题解:

题解:

class Solution {public int minimumSeconds(List<Integer> nums) {HashMap<Integer, List<Integer>> mp = new HashMap<>();int n = nums.size(), res = n;for (int i = 0; i < n; ++i) {mp.computeIfAbsent(nums.get(i), k -> new ArrayList<>()).add(i);}for (List<Integer> positions : mp.values()) {int mx = positions.get(0) + n - positions.get(positions.size() - 1);for (int i = 1; i < positions.size(); ++i) {mx = Math.max(mx, positions.get(i) - positions.get(i - 1));}res = Math.min(res, mx / 2);}return res;}
}

注意:
mp.computeIfAbsent(nums.get(i), k -> new ArrayList<>()).add(i);的意思表示key为“i”的键值对是否存在

  • 如果存在则获取i的值,并操作值的list添加数据“i"。
  • 如果不存在,则调用方法,新创建list结构,将"i"添加到list中,再存入到hashMap中。
  • – 这个API适合用于值为集合的

values(): 返回Map集合中所有value组成的以Collection数据类型格式数据。

如果大家有什么思考和问题,可以在评论区讨论,也可以私信我,很乐意为大家效劳。
好啦,今天的每日一题到这里就结束了,如果大家觉得有用,可以可以给我一个小小的赞呢,我们下期再见!

这篇关于算法每日一题: 使用循环数组所有元素相等的最少秒数 | 哈希的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/680364

相关文章

Python通用唯一标识符模块uuid使用案例详解

《Python通用唯一标识符模块uuid使用案例详解》Pythonuuid模块用于生成128位全局唯一标识符,支持UUID1-5版本,适用于分布式系统、数据库主键等场景,需注意隐私、碰撞概率及存储优... 目录简介核心功能1. UUID版本2. UUID属性3. 命名空间使用场景1. 生成唯一标识符2. 数

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr

Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

《Androidkotlin中Channel和Flow的区别和选择使用场景分析》Kotlin协程中,Flow是冷数据流,按需触发,适合响应式数据处理;Channel是热数据流,持续发送,支持... 目录一、基本概念界定FlowChannel二、核心特性对比数据生产触发条件生产与消费的关系背压处理机制生命周期

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》:本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

SpringBoot线程池配置使用示例详解

《SpringBoot线程池配置使用示例详解》SpringBoot集成@Async注解,支持线程池参数配置(核心数、队列容量、拒绝策略等)及生命周期管理,结合监控与任务装饰器,提升异步处理效率与系统... 目录一、核心特性二、添加依赖三、参数详解四、配置线程池五、应用实践代码说明拒绝策略(Rejected

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

Ubuntu如何分配​​未使用的空间

《Ubuntu如何分配​​未使用的空间》Ubuntu磁盘空间不足,实际未分配空间8.2G因LVM卷组名称格式差异(双破折号误写)导致无法扩展,确认正确卷组名后,使用lvextend和resize2fs... 目录1:原因2:操作3:报错5:解决问题:确认卷组名称​6:再次操作7:验证扩展是否成功8:问题已解

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构

使用Docker构建Python Flask程序的详细教程

《使用Docker构建PythonFlask程序的详细教程》在当今的软件开发领域,容器化技术正变得越来越流行,而Docker无疑是其中的佼佼者,本文我们就来聊聊如何使用Docker构建一个简单的Py... 目录引言一、准备工作二、创建 Flask 应用程序三、创建 dockerfile四、构建 Docker