本文主要是介绍LeetCode每日一题 | 2808. 使循环数组所有元素相等的最少秒数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 题目描述
- 问题分析
- 程序代码
题目描述
原题链接
给你一个下标从 0 开始长度为 n 的数组 nums 。
每一秒,你可以对数组执行以下操作:
- 对于范围在
[0, n - 1]
内的每一个下标i
,将nums[i]
替换成nums[i]
,nums[(i - 1 + n) % n]
或者nums[(i + 1) % n]
三者之一。
注意,所有元素会被同时替换。
请你返回将数组 nums 中所有元素变成相等元素所需要的 最少 秒数。
问题分析
仔细观察可以发现,这道题可以转为求循环数组中,相同元素x,之间邻接的最大距离最小。
因此,我们可以用一个哈希 map 存储相同元素的所有下标,然后计算相邻坐标之间的差值,得到全局的最大距离最小mx
。
最终的结果就是mx / 2
,即向下取整。
程序代码
class Solution {
public:int minimumSeconds(vector<int>& nums) {unordered_map<int, vector<int>> mp;int n = nums.size(), res = n;for(int i = 0; i < n; i++) {mp[nums[i]].push_back(i);}for(auto t : mp) {int mx = t.second[0] + n - t.second.back();for(int i = 1; i < t.second.size(); i++) {mx = max(mx, t.second[i] - t.second[i-1]);}res = min(res, mx / 2);}return res;}
};
这篇关于LeetCode每日一题 | 2808. 使循环数组所有元素相等的最少秒数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!