Hard

题目描述

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

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

  • 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，到达数组的最后一个下标。

提示：

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

解题思路

这是一个典型的最短路径问题，可以用 BFS 求解。关键在于如何建图和优化搜索过程。

核心思路：

  1. 将数组索引看作图的节点，每个索引 i 可以连接到 i+1、i-1 和所有与 arr[i] 值相同的索引 j
  2. 使用哈希表预处理，建立值到索引列表的映射关系
  3. 从索引 0 开始 BFS，目标是到达索引 n-1

优化要点：

  • 使用哈希表存储每个值对应的所有索引，避免重复遍历
  • 一旦访问过某个值的所有相同索引后，清空该值的索引列表，防止重复访问
  • 使用 visited 数组记录已访问的索引

时间复杂度分析：

  • 预处理建图：O(n)
  • BFS 搜索：每个节点最多访问一次，每条边最多遍历一次，总体 O(n)
  • 整体时间复杂度：O(n)

这种方法既保证了找到最短路径，又通过优化避免了重复搜索，是这类问题的标准解法。

代码实现

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        if (n == 1) return 0;
        
        unordered_map<int, vector<int>> valueToIndices;
        for (int i = 0; i < n; i++) {
            valueToIndices[arr[i]].push_back(i);
        }
        
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(0);
        visited[0] = true;
        
        int steps = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int curr = q.front();
                q.pop();
                
                if (curr == n - 1) return steps;
                
                // Jump to i+1
                if (curr + 1 < n && !visited[curr + 1]) {
                    visited[curr + 1] = true;
                    q.push(curr + 1);
                }
                
                // Jump to i-1
                if (curr - 1 >= 0 && !visited[curr - 1]) {
                    visited[curr - 1] = true;
                    q.push(curr - 1);
                }
                
                // Jump to same value indices
                for (int next : valueToIndices[arr[curr]]) {
                    if (!visited[next]) {
                        visited[next] = true;
                        q.push(next);
                    }
                }
                valueToIndices[arr[curr]].clear();
            }
            steps++;
        }
        
        return -1;
    }
};

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 1:
            return 0
        
        value_to_indices = defaultdict(list)
        for i, val in enumerate(arr):
            value_to_indices[val].append(i)
        
        visited = [False] * n
        queue = deque([0])
        visited[0] = True
        
        steps = 0
        while queue:
            for _ in range(len(queue)):
                curr = queue.popleft()
                
                if curr == n - 1:
                    return steps
                
                # Jump to i+1
                if curr + 1 < n and not visited[curr + 1]:
                    visited[curr + 1] = True
                    queue.append(curr + 1)
                
                # Jump to i-1
                if curr - 1 >= 0 and not visited[curr - 1]:
                    visited[curr - 1] = True
                    queue.append(curr - 1)
                
                # Jump to same value indices
                for next_idx in value_to_indices[arr[curr]]:
                    if not visited[next_idx]:
                        visited[next_idx] = True
                        queue.append(next_idx)
                
                value_to_indices[arr[curr]].clear()
            
            steps += 1
        
        return -1

public class Solution {
    public int MinJumps(int[] arr) {
        int n = arr.Length;
        if (n == 1) return 0;
        
        Dictionary<int, List<int>> valueToIndices = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++) {
            if (!valueToIndices.ContainsKey(arr[i])) {
                valueToIndices[arr[i]] = new List<int>();
            }
            valueToIndices[arr[i]].Add(i);
        }
        
        bool[] visited = new bool[n];
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(0);
        visited[0] = true;
        
        int steps = 0;
        while (queue.Count > 0) {
            int size = queue.Count;
            for (int i = 0; i < size; i++) {
                int curr = queue.Dequeue();
                
                if (curr == n - 1) return steps;
                
                // Jump to i+1
                if (curr + 1 < n && !visited[curr + 1]) {
                    visited[curr + 1] = true;
                    queue.Enqueue(curr + 1);
                }
                
                // Jump to i-1
                if (curr - 1 >= 0 && !visited[curr - 1]) {
                    visited[curr - 1] = true;
                    queue.Enqueue(curr - 1);
                }
                
                // Jump to same value indices
                if (valueToIndices.ContainsKey(arr[curr])) {
                    foreach (int next in valueToIndices[arr[curr]]) {
                        if (!visited[next]) {
                            visited[next] = true;
                            queue.Enqueue(next);
                        }
                    }
                    valueToIndices[arr[curr]].Clear();
                }
            }
            steps++;
        }
        
        return -1;
    }
}

var minJumps = function(arr) {
    const n = arr.length;
    if (n <= 1) return 0;
    
    const valueMap = new Map();
    for (let i = 0; i < n; i++) {
        if (!valueMap.has(arr[i])) {
            valueMap.set(arr[i], []);
        }
        valueMap.get(arr[i]).push(i);
    }
    
    const visited = new Set();
    const queue = [0];
    visited.add(0);
    let steps = 0;
    
    while (queue.length > 0) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const curr = queue.shift();
            
            if (curr === n - 1) return steps;
            
            const neighbors = [];
            if (curr - 1 >= 0) neighbors.push(curr - 1);
            if (curr + 1 < n) neighbors.push(curr + 1);
            
            if (valueMap.has(arr[curr])) {
                neighbors.push(...valueMap.get(arr[curr]));
                valueMap.delete(arr[curr]);
            }
            
            for (const next of neighbors) {
                if (!visited.has(next)) {
                    visited.add(next);
                    queue.push(next);
                }
            }
        }
        steps++;
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)预处理建图 O(n)，BFS 中每个节点最多访问一次，每条边最多遍历一次
空间复杂度O(n)哈希表存储索引映射，visited 数组和队列的空间开销

相关题目