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

相关文章

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

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

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

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

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定