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;}
};