LeetCode.2808. 使循环数组所有元素相等的最少秒数

题目

题目链接

分析

我们最终形成的数组一定是当前数组nums 中的一个数字。
所以我们的想法就是枚举数组 nums 中的所有数字，取最小值。

题目告诉我们每一秒都可以向左右扩散一位，那么多个相同的 x 同时扩散，扩散完整个数组耗时就取决于两个相邻最远的 x 的距离。

假设这两个 x 的下标为 i 和 j，且 i < j，那么耗时就是：(j - i) / 2

枚举数组不同的，取最小值，即为答案。

因为本题中数组被看成环形状，所以在计算距离的时候 我们需要将首个元素+数组长度再次放入列表中，这样就可以处理环形了。

代码

class Solution {
    public int minimumSeconds(List<Integer> nums) {
        int n = nums.size();
        Map<Integer,List<Integer>> pos = new HashMap<>();
        for(int i = 0;i < n;i ++) {
            // 元素,List<所有下标>
            pos.computeIfAbsent(nums.get(i),k -> new ArrayList<>()).add(i);
        }

        int ans = n;
        for(List<Integer> a : pos.values()) {
            // 将首个位置的索引+n，考虑了环
            a.add(a.get(0) + n);
            int mx = 0;
            for(int i = 1;i < a.size();i ++) {
                // 统计每两个元素之间的最大距离
                mx= Math.max(mx,a.get(i) - a.get(i - 1));
            }
            ans = Math.min(ans,mx);
        }
        return ans / 2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23