本文主要是介绍【数组】【最长距离】使循环数组所有元素相等的最少秒数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
本文涉及知识点
数组 最长距离
LeetCode2808. 使循环数组所有元素相等的最少秒数
给你一个下标从 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
枚举
本题 ⟺ \iff ⟺ 一个病毒可以向左右各传播一位,最快多短时间传播到整个数组。
mIndexs 的key是值,value是此值所有的下标升序。
枚举各值传播到整个数组的时间。
v[i]到v[i+1]之间的数,显然最中间的数,最难传染。假定中间的数数量是x,需要传播的时间为:
{ x / 2 x 是偶数 ( x + 1 ) / 2 x 是奇数 \begin{cases} x/2 && x是偶数 \\ (x+1)/2 && x是奇数\\ \end{cases} {x/2(x+1)/2x是偶数x是奇数
可以统一为 (x+1)/2。
v[0]之前,v.back()之后的也要统一处理。其实v[1].size()等于0,也无需特殊处理。
代码
核心代码
class Solution {public:int minimumSeconds(vector<int>& nums) {const int n = nums.size();unordered_map<int, vector<int>> mIndexs;for (int i = 0; i < n ; i++){mIndexs[nums[i]].emplace_back(i);}int iRet = (nums.size()-1+1)/2;for (const auto& [tmp, v] : mIndexs){if (1 == v.size()) {continue;}int iMaxCnt = n - 1 - v.back() + v.front();for (int i = 1; i < v.size(); i++){iMaxCnt = max(iMaxCnt, v[i] - v[i - 1] - 1);}iRet = min(iRet, (iMaxCnt + 1) / 2);}return iRet;}};
测试用例
vector<int> nums = { 2, 1, 3, 3, 2 };{Solution sln;nums = { 2, 1, 3, 3, 2 };auto res = sln.minimumSeconds(nums);Assert(res, 2);}{Solution sln;nums = { 1,2,3 };auto res = sln.minimumSeconds(nums);Assert(res, 1);}
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话 |
---|
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。
这篇关于【数组】【最长距离】使循环数组所有元素相等的最少秒数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!