本文主要是介绍每日打卡 力扣2808 使循环数组所有元素相等的最少秒数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
2808. 使循环数组所有元素相等的最少秒数
题目描述:
给你一个下标从 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^5
1 <= nums[i] <= 10^9
思路:
我们首先用哈希表,统计 nums中相同的数所出现的位置,mp[x]\表示 x所出现的位置。
然后我们研究,使得数组全部变为 x所需要的时间,这个时间取决于 nums 中,相邻 x 的最大距离。我们依次枚举所有相邻(包括头尾)x 的索引值,找到最大的距离。最大距离除以二并向下取整,就是使得数组全部变为 x 所需要的时间。
最后我们对所有 nums中 的数,都找到所需的时间,返回其中的最小值即可。
代码:
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;}};
class Solution:def minimumSeconds(self, nums: List[int]) -> int:num_idxs = {} # 存储每个元素出现的位置n = len(nums)for i, num in enumerate(nums):if num not in num_idxs:num_idxs[num] = []num_idxs[nums[i]].append(i)res = n + 1 # 初始为一个极大值,数组长度+1for _, idxes in num_idxs.items():need_seconds = 0 # 元素it.first覆盖整个数组需要的时间idxes.append(idxes[0] + n) # 将首个位置的索引+n,计算首个位置和最后一个位置之间的环形巨鹿for i in range(1, len(idxes)):need_seconds = max(need_seconds, (idxes[i] - idxes[i-1]) // 2) # 统计每两个元素之间需要覆盖的时间,取最大覆盖时间res = min(res, need_seconds)return res
这篇关于每日打卡 力扣2808 使循环数组所有元素相等的最少秒数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!