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

  • 对于范围在[0, n - 1]内的每一个下标i,将nums[i]替换成nums[i],nums[(i - 1 + n)
  • 注意,所有元素会被同时替换。

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

输入格式

输入为一个数组nums。

输出格式

输出为一个整数,表示需要的最少秒数。

数据范围

1 <= n == nums.length <= 105

1 <= nums[i] <= 109

示例

输入样例:

nums = [1,2,1,2]

输出样例:

1

解释:我们可以在 1 秒内将数组变成相等元素:

  • 第 1 秒,将每个位置的元素分别变为 [nums[3],nums[1],nums[3],nums[3]] 。变化后,nums = [2,2,2,2] 。 1 秒是将数组变成相等元素所需要的最少秒数。

输入样例:

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 秒是将数组变成相等元素所需要的最少秒数。

输入样例:

nums = [5,5,5,5]

输出样例:

0

解释:不需要执行任何操作,因为一开始数组中的元素已经全部相等。

题目分析

可以发现, 相邻 元素 的最大距离除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& pos : mp) {
            int mx = pos.second[0] + n - pos.second.back();
            for (int i = 1; i < pos.second.size(); ++i) {
                mx = max(mx, pos.second[i] - pos.second[i - 1]);
            }
            res = min(res, mx / 2);
        }
        return res;
    }
};
分类: BFSThought

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status