2808.使循环数组所有元素相等的最少秒数

【LetMeFly】2808.使循环数组所有元素相等的最少秒数

力扣题目链接：https://leetcode.cn/problems/minimum-seconds-to-equalize-a-circular-array/

给你一个下标从 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

方法一：哈希表

其实不难发现，最终数组中元素的值一定是数组中某个原有元素的值。

因此使用一个哈希表，记录每个元素$a$在nums数组中出现的位置。

这样，假设数组中所有元素最终都变成了$a$，那么我们只需要枚举$a$在原始数组中的所有出现位置，间隔最大的两个位置决定了“感染其他元素”所需要的时间。

枚举原始数组中所有出现过的元素（哈希表的键值），对于这个元素的所有出现位置，假设间距最大的是$thisMax$，则将数组权变成这个元素所需最小时间为$\lfloor\frac{thisMax}2\rfloor$。

所有的最小时间中最小的那个即为答案。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(len(nums))$

AC代码

C++

class Solution {
public:
    int minimumSeconds(vector<int>& nums) {
        unordered_map<int, vector<int>> ma;
        for (int i = 0; i < nums.size(); i++) {
            ma[nums[i]].push_back(i);
        }
        int ans = nums.size() - 1;
        for (auto&& [num, positions] : ma) {
            int thisMax = positions[0] + nums.size() - positions.back();
            for (int i = 1; i < positions.size(); i++) {
                thisMax = max(thisMax, positions[i] - positions[i - 1]);
            }
            ans = min(ans, thisMax / 2);
        }
        return ans;
    }
};

Python

# from typing import List
# from collections import defaultdict

class Solution:
    def minimumSeconds(self, nums: List[int]) -> int:
        ma = defaultdict(list)
        for i, val in enumerate(nums):
            ma[val].append(i)
        ans = len(nums) - 1
        for num, positions in ma.items():
            thisMax = positions[0] + len(nums) - positions[-1]
            for i in range(1, len(positions)):
                thisMax = max(thisMax, positions[i] - positions[i - 1])
            ans = min(ans, thisMax // 2)
        return ans

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/135930013