1345. 跳跃游戏 IV

题目

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标 i + 1 、i - 1 或者 j ：

i + 1 需满足：i + 1 < arr.length
i - 1 需满足：i - 1 >= 0
j 需满足：arr[i] == arr[j] 且 i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

示例 1：

输入：arr = [100,-23,-23,404,100,23,23,23,3,404]
输出：3
解释：那你需要跳跃 3 次，下标依次为 0 —> 4 —> 3 —> 9 。下标 9 为数组的最后一个元素的下标。
示例 2：

输入：arr = [7]
输出：0
解释：一开始就在最后一个元素处，所以你不需要跳跃。
示例 3：

输入：arr = [7,6,9,6,9,6,9,7]
输出：1
解释：你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。
示例 4：

输入：arr = [6,1,9]
输出：2
示例 5：

输入：arr = [11,22,7,7,7,7,7,7,7,22,13]
输出：3

提示：

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

思路

和第三题差不多，不同的是这题可以跳到和自己值相同的位置，因此使用一个哈希表记录一下每个元素出现的下标，另外，这题求的是最少步数，因此要用广度优先遍历。这其实是一个无向图的最短路问题。

结果第一次提交超时了，当数组绝大多数相同时就可能会超时，因为时间复杂度是#card=math&code=O%28V%2BE%29&id=Eeg5x)，即点和边数之和，而这种情况的边数太多了，达到，所以超时。

其实，值相同的位置只需要入队一次，当遍历第一个顶点使所有顶点都入队后，其余所有顶点都不再需要第二次入队，也即不再需要访问哈希表相同的键了，因此可以将其移除。

代码

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }
        boolean[] visited = new boolean[n];
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(0);
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int cur = q.poll();
                if (cur == n - 1) {
                    return step;
                }
                if (cur + 1 < n && !visited[cur + 1]) {
                    q.offer(cur + 1);
                    visited[cur + 1] = true;
                }
                if (cur - 1 >= 0 && !visited[cur - 1]) {
                    q.offer(cur - 1);
                    visited[cur - 1] = true;
                }
                // 第一版超时，第一次遍历完入队后就不再需要访问了，因此可以删除了
                if (map.containsKey(arr[cur])) {
                    for (int k : map.get(arr[cur])) {
                        if (k != cur && !visited[k]) {
                            q.offer(k);
                            visited[k] = true;
                        }
                        map.remove(arr[cur]);
                    }
                }
            }
            step++;
        }
        return step;
    }
}