题目描述
给你一个下标从 0 开始长度为 n
的数组 nums
。
每一秒,你可以对数组执行以下操作:
- 对于范围在
[0, n - 1]
内的每一个下标i
,将nums[i]
替换成nums[i]
,nums[(i - 1 + n) % n]
或者nums[(i + 1) % n]
三者之一。
注意,所有元素会被同时替换。
请你返回将数组 nums
中所有元素变成相等元素所需要的 最少 秒数。
样例
输入: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
解释:不需要执行任何操作,因为一开始数组中的元素已经全部相等。
限制
1 <= n == nums.length <= 10^5
1 <= nums[i] <= 10^9
算法
(哈希表) $O(n)$
- 假设选定了一个目标数字 $t$ 和若干个和这个等于目标数字的初始位置,这些位置之间的最大距离为 $k$,则仅需要 $k/2$ 秒可以使得整个数组都变为 $t$。
- 使用哈希表存储每个数字的所有出现位置。
- 遍历哈希表,找到数字对应所有位置中,最大间隔距离最小的那个数字,得到对应的间隔距离,进而求出答案。
时间复杂度
- 遍历数组一次,遍历哈希表一次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
class Solution {
public:
int minimumSeconds(vector<int>& nums) {
const int n = nums.size();
unordered_map<int, vector<int>> v;
for (int i = 0; i < n; i++)
v[nums[i]].push_back(i);
int ans = n / 2;
for (const auto &[_, v] : v) {
int m = n + v[0] - v.back();
for (int i = 0; i < v.size() - 1; i++)
m = max(m, v[i + 1] - v[i]);
ans = min(ans, m / 2);
}
return ans;
}
};