2024.1.30力扣每日一题——使循环数组所有元素相等的最少秒数

本文主要是介绍2024.1.30力扣每日一题——使循环数组所有元素相等的最少秒数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024.1.30

- - 题目来源
  - 我的题解
  - - 方法一暴力+模拟（无法通过）
    - 方法二哈希表+数学

题目来源

力扣每日一题；题序：2808

我的题解

方法一暴力+模拟（无法通过）

直接暴力枚举。记录每一个元素所在的位置，然后模拟光源扩散，每次扩散左右各一个索引。

时间复杂度：O(nmlogn)。其中n表示nums的大小，m表示nums中不同元素的个数
空间复杂度：O(n)。哈希表所需要的空间

public int minimumSeconds(List<Integer> nums) {int n=nums.size();Map<Integer,List<Integer>> map=new HashMap<>();for(int i=0;i<n;i++){int num=nums.get(i);List<Integer> t=map.getOrDefault(num,new ArrayList<>());t.add(i);map.put(num,t);}int res=Integer.MAX_VALUE;for(int key:map.keySet()){res=Math.min(res,getTime(map.get(key),n));}return res;
}
public int getTime(List<Integer> list,int n){int res=0;int max_size=list.size();Set<Integer> cand=new HashSet<>(list);while(max_size!=n){List<Integer> t=new ArrayList<>(cand);for(int i:t){int pre=((i-1)+n)%n;int next=(i+1)%n;if(!cand.contains(pre))cand.add(pre);if(!cand.contains(next))cand.add(next);}res++;max_size=cand.size();}return res;
}

方法二哈希表+数学

参考：官方题解

对于getTime函数中为什么这么做，没怎么看懂。以下是评论区的大佬的解答：
可以理解成仅能双向发散的光源，在有限空间中完成扩散需要的时间（速度为每秒一个索引），对于多个光源（相同数），扩散完成的时间取决于相隔最远（水桶效应）的两个光源双向奔赴的时间（最大距离除以二）。用索引相减计算出的距离实际上比相隔元素数多一，所以最终花费时间还要向下取整，如果用相隔元素数量表示距离，那时间就是向上取整。

时间复杂度：O( $n^2$ )
空间复杂度：O(n)

public int minimumSeconds(List<Integer> nums) {int n=nums.size();Map<Integer,List<Integer>> map=new HashMap<>();for(int i=0;i<n;i++){int num=nums.get(i);List<Integer> t=map.getOrDefault(num,new ArrayList<>());t.add(i);map.put(num,t);}int res=Integer.MAX_VALUE;for(int key:map.keySet()){res=Math.min(res,getTime(map.get(key),n));}return res;
}
public int getTime(List<Integer> list,int n){int res=n;int mx = list.get(0) + n - list.get(list.size() - 1);for (int i = 1; i < list.size(); ++i) {mx = Math.max(mx, list.get(i) - list.get(i - 1));}res = Math.min(res, mx / 2);return res;
}