LeetCode 使循环数组所有元素相等的最少秒数

2024-01-31 15:52

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

地址:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
难度:中等

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

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

其实就是nums[i]可以替换成它本身或者它的前一位或者后一位的值,这个时候在想边缘怎么办?

把数组看出一个环,num[0]挨着的就是num[8]和num[1]
可以带入计算一下:n = 9 ,i = 0,
(i - 1 + n) % n = (0-1+9)%9 = 8
(i +1 + n) % n = (0+1+9)%9 = 10%9 = 1


注意,所有元素会被同时替换。

也就是一轮替换就是1s
比如可以同时操作num[1]、num[2])替换,等这一轮停止操作了我们得到了一个替换后的数组
入果这个数组没有符合预期,那就需要再进行到下一轮替换

请你返回将数组 nums 中所有元素变成相等元素所需要的 最少 秒数。

思考过程

可以理解为将数组的每一个元素都逐渐替换为数组中的某个值。
我们可以枚举数组中的各种元素,分别计算将所有元素替换为该元素所消耗的时间。
计算过程需要利用该元素在数组中出现的位置

题解

  • 我们首先用哈希表,统计 nums 中相同的数所出现的位置,mp[x]表示 x 所出现的位置。
  • 然后我们研究,使得数组全部变为 x所需要的时间,这个时间取决于 nums中,相邻 x 的最大距离。
  • 我们依次枚举所有相邻(包括头尾)x 的索引值,找到最大的距离。
  • 最大距离除以二并向上取整,就是使得数组全部变为 x 所需要的时间
  • 最后我们对所有 nums中 的数,都找到所需的时间,返回其中的最小值即可。

本质上是扩散的原理

假设现在数组的为 3 2 6 4 9 5 3 1,x是3

分析:
我们能看到两个3之间最大的间隔有5个元素,那需要经过多少轮才能把3之间的元素同步扩散完呢?

第一次扩散(暂时不要关注数字1):

第二次扩散(暂时不要关注数字1):

第三次扩散(暂时不要关注数字1):

可以看到是经过了三次才完成了扩散,正好是5/2在向上取整的结果

为什么是除2?
因为每次两边都能同时扩散推进一个,效率是乘2的,自然最后计算的时候也就是除2啦

那短距离的那边怎么统计呢?
题目说了:所有元素会被同时替换。
也就是说,元素的扩散是同时进行的,长的距离扩散的时候,短的距离也在同步扩散,那个1在第一轮扩散的时候就被替换成3了
时间长的都扩散完了,时间短的其实早就扩散完毕了

代码解析:

function minimumSeconds(nums: number[]): number {const n:number = nums.lengthlet rs:number = nconst mp:Map<number,number[]> = new Map() //存储结果for(let i:number = 0;i<n;i++){if (!mp.has(nums[i])) {mp.set(nums[i], []);}mp.get(nums[i]).push(i);}for(const pos of mp.values()){let mx: number = pos[0] + n - pos[pos.length - 1]-1;//为什么设置这个初始值?// 避免环形的时候最大距离计算错误for (let i: number = 1; i < pos.length; ++i) {mx = Math.max(mx, pos[i] - pos[i - 1]-1);}rs = Math.min(rs, Math.ceil(mx / 2));}return rs
};

解释一下这行代码:number = pos[0] + n - pos[pos.length - 1]-1

我们知道我们需要找到的是最大距离,记住数组是环形数组
那么下面的情况,最大长度就会是pos[0] + n - pos[pos.length - 1]-1

如果我们还是拿2-0-1的话,计算出来的是短的距离,结果是1,会导致最终的答案不对

这篇关于LeetCode 使循环数组所有元素相等的最少秒数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件