英文原文
Given an array of integers arr, you are initially positioned at the first index of the array.
In one step you can jump from index i to index:
i + 1where:i + 1 < arr.length.i - 1where:i - 1 >= 0.jwhere:arr[i] == arr[j]andi != j.
Return the minimum number of steps to reach the last index of the array.
Notice that you can not jump outside of the array at any time.
Example 1:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404] Output: 3 Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
Example 2:
Input: arr = [7] Output: 0 Explanation: Start index is the last index. You don't need to jump.
Example 3:
Input: arr = [7,6,9,6,9,6,9,7] Output: 1 Explanation: You can jump directly from index 0 to index 7 which is last index of the array.
Example 4:
Input: arr = [6,1,9] Output: 2
Example 5:
Input: arr = [11,22,7,7,7,7,7,7,7,22,13] Output: 3
Constraints:
1 <= arr.length <= 5 * 104-108 <= arr[i] <= 108
中文题目
给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标：
i + 1满足：i + 1 < arr.lengthi - 1满足：i - 1 >= 0j满足：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
通过代码
高赞题解
题目描述 给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。
每一步，你可以从下标 i 跳到下标：
i + 1满足：i + 1 < arr.length
i - 1满足：i - 1 >= 0j满足：arr[i] == arr[j]且i != j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意：任何时候你都不能跳到数组外面。
分析 最短路问题，考虑BFS做法。写出最基本的BFS方法，伪代码如下：
q.push(u), vis[u] = 1, dis[u] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v in {u+1, u-1}) {
// 左右跳跃
if (v >= 0 && v < n && !vis[v]) {
vis[v] = 1, q.push(v), dis[v] = dis[u]+1;
}
// 同值跳跃
for (int v = 0; v < n; v++) {
if (u != v && a[v] == a[u] && !vis[v]) {
vis[v] = 1, q.push(v), dis[v] = dis[u]+1;
}
}
}
}但是这个代码复杂度为 $O(n^2)$ ，选择同值的跳跃方法太耗时，遍历需要$O(n)$。
这里使用倒排加速，即开一个哈希表k->v记录所有使得a[k]=v的k：
unordered_map<int, vector<int>> m;
for (int i = 0; i < n; i++) m[a[i]].push_back(i);但是即使这样，选择同值进行跳跃的复杂度仍然是$O(n)$。BFS的特点是每个点只进入队列一次，且进入队列的点的距离严格单调不递减。而同值跳跃的特点是，一旦一个值被访问了（除了开始的点），同值的所有点全部都被访问。所以，一旦发生了同值跳跃，任何同值的都不会再被跳跃。那么当我们跳跃过一个值之后，就可以记录下来，不再跳跃该值。修改之前的代码，得到：
class Solution {
public:
int minJumps(vector<int>& arr) {
int n = arr.size();
vector<int> dis(n, INT_MAX); // 距离
vector<int> vis(n, 0); // 访问标记
unordered_map<int, vector<int>> m; // 倒排加速(m既起到了倒排加速作用，又起到了记录值是否被访问的作用，如果有一个值被访问过了，删除该值对应的键)
for (int i = 0; i < n-1; i++)
m[arr[i]].push_back(i);
dis[n-1] = 0; // 最后一个点入队
queue<int> q;
q.push(n-1);
while (!q.empty()) {
int u = q.front();
q.pop();
if (u-1 >= 0 && !vis[u-1] && m.find(arr[u-1]) != m.end()) { // 左跳（其中m判断了该值是否被访问过）
dis[u-1] = min(dis[u-1], dis[u]+1);
vis[u-1] = 1;
q.push(u-1);
}
if (u+1 < n && !vis[u+1] && m.find(arr[u+1]) != m.end()) { // 右跳
dis[u+1] = min(dis[u+1], dis[u]+1);
vis[u+1] = 1;
q.push(u+1);
}
if (m.find(arr[u]) != m.end()) {
for (int v: m[arr[u]]) {
if (!vis[v]) {
vis[v] = 1;
dis[v] = min(dis[u]+1, dis[v]);
q.push(v);
}
}
m.erase(arr[u]); // 访问过的值直接清理掉
}
}
return dis[0];
}
};时间复杂度分析 $O(n)$ 每个元素入队出队均只有一次，倒排哈希表的加入和删除都只有一次。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 6078 | 16742 | 36.3% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
