【数组】【最长距离】使循环数组所有元素相等的最少秒数

本文涉及知识点

数组 最长距离

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 <= 10⁵

1 <= nums[i] <= 10⁹

枚举

本题   ⟺    \iff⟺ 一个病毒可以向左右各传播一位，最快多短时间传播到整个数组。

mIndexs 的key是值，value是此值所有的下标升序。

枚举各值传播到整个数组的时间。

v[i]到v[i+1]之间的数，显然最中间的数，最难传染。假定中间的数数量是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++**实现。