题目描述

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

每一步，你可以从下标 i 跳到下标：

• i + 1 满足：i + 1 < arr.length
• i - 1 满足：i - 1 >= 0
• j 满足：arr[i] == arr[j] 且 i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数。

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

样例

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

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

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

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

输入：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

算法

(宽度优先遍历) $O(n)$

1. 用一个哈希表记录每种数字的所有位置。
2. 每个位置看做一个点，从 0 号点开始宽度优先遍历。
3. 转移的三种，向前走，向后走，以及通过相等的点进行转移。
4. 这里需要一个优化，如果某个数字用过了“通过相等转移”，则再遇到该数字时不再进行“通过相等转移”。因为转移后的结果必定不如之前优。

时间复杂度

• 每个点仅遍历一次，转移时每个位置仅被枚举常数次，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存放哈希表，存放队列以及记录距离。

C++ 代码

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int, vector<int>> mp;
        unordered_map<int, bool> vis;

        for (int i = 0; i < n; i++) {
            mp[arr[i]].push_back(i);
            vis[arr[i]] = false;
        }

        queue<int> q;
        vector<int> dis(n, n + 1);

        q.push(0);
        dis[0] = 0;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            if (u > 0 && dis[u - 1] > dis[u] + 1) {
                dis[u - 1] = dis[u] + 1;
                q.push(u - 1);
            }

            if (u < n - 1 && dis[u + 1] > dis[u] + 1) {
                dis[u + 1] = dis[u] + 1;
                q.push(u + 1);
            }

            if (!vis[arr[u]]) {
                for (int v : mp[arr[u]])
                    if (dis[v] > dis[u] + 1) {
                        dis[v] = dis[u] + 1;
                        q.push(v);
                    }
                vis[arr[u]] = true;
            }
        }

        return dis[n - 1];
    }
};