广州知名网站设计,想要找个网站做环评公示,进入网上商城,网络维护工资多少一个月2024.1.30 题目来源我的题解方法一 暴力模拟#xff08;无法通过#xff09;方法二 哈希表数学 题目来源
力扣每日一题#xff1b;题序#xff1a;2808
我的题解
方法一 暴力模拟#xff08;无法通过#xff09; 直接暴力枚举。记录每一个元素所在的位置#xff0c;然… 2024.1.30 题目来源我的题解方法一 暴力模拟无法通过方法二 哈希表数学 题目来源
力扣每日一题题序2808
我的题解
方法一 暴力模拟无法通过 直接暴力枚举。记录每一个元素所在的位置然后模拟光源扩散每次扩散左右各一个索引。 时间复杂度O(nmlogn)。其中n表示nums的大小m表示nums中不同元素的个数 空间复杂度O(n)。哈希表所需要的空间 public int minimumSeconds(ListInteger nums) {int nnums.size();MapInteger,ListInteger mapnew HashMap();for(int i0;in;i){int numnums.get(i);ListInteger tmap.getOrDefault(num,new ArrayList());t.add(i);map.put(num,t);}int resInteger.MAX_VALUE;for(int key:map.keySet()){resMath.min(res,getTime(map.get(key),n));}return res;
}
public int getTime(ListInteger list,int n){int res0;int max_sizelist.size();SetInteger candnew HashSet(list);while(max_size!n){ListInteger tnew ArrayList(cand);for(int i:t){int pre((i-1)n)%n;int next(i1)%n;if(!cand.contains(pre))cand.add(pre);if(!cand.contains(next))cand.add(next);}res;max_sizecand.size();}return res;
}
方法二 哈希表数学
参考官方题解 对于getTime函数中为什么这么做没怎么看懂。以下是评论区的大佬的解答 可以理解成仅能双向发散的光源在有限空间中完成扩散需要的时间速度为每秒一个索引对于多个光源相同数扩散完成的时间取决于相隔最远水桶效应的两个光源双向奔赴的时间最大距离除以二。用索引相减计算出的距离实际上比相隔元素数多一所以最终花费时间还要向下取整如果用相隔元素数量表示距离那时间就是向上取整。 时间复杂度O( n 2 n^2 n2) 空间复杂度O(n) public int minimumSeconds(ListInteger nums) {int nnums.size();MapInteger,ListInteger mapnew HashMap();for(int i0;in;i){int numnums.get(i);ListInteger tmap.getOrDefault(num,new ArrayList());t.add(i);map.put(num,t);}int resInteger.MAX_VALUE;for(int key:map.keySet()){resMath.min(res,getTime(map.get(key),n));}return res;
}
public int getTime(ListInteger list,int n){int resn;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;
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
