本文主要是介绍LeetCode解法汇总2808. 使循环数组所有元素相等的最少秒数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录链接:
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目:
https://github.com/September26/java-algorithms
原题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
描述:
给你一个下标从 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
解题思路:
每次只能修改相邻的,所以决定一个数字多少次可以修改完,则需要找到同一个数字相间隔的最远距离即可。
所以我们首先统计一下每个值所对应的位置,减少遍历次数。
然后遍历每个值所对应的位置集合,找出想间隔最远的距离,这就这个值所需要的最少秒数。求出所有值的最小秒数即可。
代码:
public class Solution2808 {public int minimumSeconds(List<Integer> nums) {Map<Integer, List<Integer>> map = new HashMap<>();for (int i = 0; i < nums.size(); i++) {List<Integer> integers = map.computeIfAbsent(nums.get(i), k -> new ArrayList<>());integers.add(i);}int abs = 100000;for (Integer key : map.keySet()) {List<Integer> integers = map.get(key);int i = computeMaxDistance(integers, nums.size());abs = Math.min(abs, i);System.out.println("key:" + key + ",value:" + i);}return abs;}private int computeMaxDistance(List<Integer> integers, int length) {int distance = 0;int lastIndex = integers.get(integers.size() - 1) - length;int index = 0;while (index < integers.size()) {Integer integer = integers.get(index);distance = Math.max(distance, (integer - lastIndex) / 2);index++;lastIndex = integer;}return distance;}
}
这篇关于LeetCode解法汇总2808. 使循环数组所有元素相等的最少秒数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!