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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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


2808.使循环数组所有元素相等的最少秒数
https://blog.letmefly.xyz/2024/01/30/LeetCode 2808.使循环数组所有元素相等的最少秒数/
作者
Tisfy
发布于
2024年1月30日
许可协议