java 如何在 O(n) 时间内找到到达数组末尾的最小跳转次数

How to find minimum number of jumps to reach the end of the array in O(n) time

提问by Walt

Question

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then cannot move through that element.

Example

Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: 3 (1-> 3 -> 8 ->9)

问题

给定一个整数数组，其中每个元素表示可以从该元素向前进行的最大步数。编写一个函数，返回到达数组末尾（从第一个元素开始）的最少跳转次数。如果元素为 0，则无法通过该元素。

例子

输入：arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
输出：3 (1-> 3 -> 8 ->9)

Found multiple ways from Dynamic Programming approachto other linear approaches. I am not able to understand the approach which is said to linear in time. HEREis the link where a linear approach is proposed.

发现了从动态规划方法到其他线性方法的多种方法。我无法理解所谓的时间线性方法。这里是提出线性方法的链接。

I am not able to understand it at all. What I could understand is that author is suggesting to do a greedy approach and see if we reach end .. if not then backtrack ?

我根本无法理解。我能理解的是，作者建议采取贪婪的方法，看看我们是否到达终点..如果没有，那么回溯？

回答by Niels Billen

The time complexity of the solution proposed on the site is linear because you only iterate over the array once. The algorithm avoids the inner iteration of my proposed solution by using some clever tricks.

该站点上提出的解决方案的时间复杂度是线性的，因为您只对数组进行一次迭代。该算法通过使用一些巧妙的技巧来避免我提出的解决方案的内部迭代。

The variable maxReachstores at all time the maximal reachable position in the array. jumpstores the amount of jumps necessary to reach that position. stepstores the amount of steps we can still take (and is initialized with the amount of steps at the first array position)

该变量maxReach始终存储数组中的最大可达位置。jump存储到达该位置所需的跳跃量。step存储我们仍然可以采取的步数（并使用第一个数组位置的步数进行初始化）

During the iteration, the above values are updated as follows:

在迭代过程中，上述值更新如下：

First we test whether we have reached the end of the array, in which case we just need to return the jumpvariable.

首先我们测试我们是否已经到达数组的末尾，在这种情况下我们只需要返回jump变量。

Next we update the maximal reachable position. This is equal to the maximum of maxReachand i+A[i](the number of steps we can take from the current position).

接下来我们更新最大可达位置。这是等于最大的maxReach和i+A[i]（在步骤我们可以从当前位置数）。

We used up a step to get to the current index, so stepshas to be decreased.

我们用了一个步骤来获得当前索引，因此steps必须减少。

If no more steps are remaining (i.e. steps=0, then we must have used a jump. Therefore increase jump. Since we know that it is possible somehow to reach maxReach, we initialize the steps to the amount of steps to reach maxReachfrom position i.

如果没有剩余的步数（即steps=0，那么我们必须使用跳跃。因此增加jump。因为我们知道有可能以某种方式到达maxReach，我们将步数初始化为maxReach从位置到达的步数i。

public class Solution {
    public int jump(int[] A) {
        if (A.length <= 1)
            return 0;
        int maxReach = A[0];
        int step = A[0];
        int jump = 1;
        for (int i = 1; i < A.length; i++) {
           if (i == A.length - 1)
                return jump;
            if (i + A[i] > maxReach)
                maxReach = i + A[i];
            step--;
            if (step == 0) {
                jump++;
                step = maxReach - i;
            } 
        }
        return jump;
    }
}

Example:

例子：

int A[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
int maxReach = A[0];     // A[0]=1, so the maximum index we can reach at the moment is 1.
int step = A[0];         // A[0] = 1, the amount of steps we can still take is also 1.
int jump = 1;            // we will always need to take at least one jump.

/*************************************
 * First iteration (i=1)
 ************************************/
if (i + A[i] > maxReach) // 1+3 > 1, we can reach further now!
    maxReach = i + A[i]  // maxReach = 4, we now know that index 4 is the largest index we can reach.

step--                   // we used a step to get to this index position, so we decrease it
if (step == 0) {
    ++jump;              // we ran out of steps, this means that we have made a jump
                         // this is indeed the case, we ran out of the 1 step we started from. jump is now equal to 2.
                         // but we can continue with the 3 steps received at array position 2.
    steps = maxReach-i   // we know that by some combination of 2 jumps, we can reach  position 4.
                         // therefore in the current situation, we can minimaly take 3
                         // more steps to reach position 4 => step = 3
}

/*************************************
 * Second iteration (i=2)
 ************************************/
if (i + A[i] > maxReach) // 2+5 > 4, we can reach further now!
    maxReach = i + A[i]  // maxReach = 7, we now know that index 7 is the largest index we can reach.

step--                   // we used a step so now step = 2
if (step==0){
   // step 
}

/*************************************
 * Second iteration (i=3)
 ************************************/
if (i + A[i] > maxReach) // 3+8 > 7, we can reach further now!
    maxReach = i + A[i]  // maxReach = 11, we now know that index 11 is the largest index we can reach.

step--                   // we used a step so now step = 1
if (step==0){
   // step 
}

/*************************************
 * Third iteration (i=4)
 ************************************/
if (i + A[i] > maxReach) // 4+9 > 11, we can reach further now!
    maxReach = i + A[i]  // maxReach = 13, we now know that index 13 is the largest index we can reach.

step--                   // we used a step so now step = 0
if (step == 0) {
    ++jump;              // we ran out of steps, this means that we have made a jump.
                         // jump is now equal to 3.
    steps = maxReach-i   // there exists a combination of jumps to reach index 13, so
                         // we still have a budget of 9 steps
}


/************************************
 * remaining iterations
 ***********************************
// nothing much changes now until we reach the end of the array.

My suboptimal algorithm which works in O(nk)time with nthe number of elements in the array and kthe largest element in the array and uses an internal loop over array[i]. This loop is avoided by the below algorithm.

我的次优算法O(nk)与n数组中的元素数量和数组中k的最大元素及时工作，并使用内部循环array[i]. 下面的算法避免了这个循环。

Code

代码

public static int minimum_steps(int[] array) {
    int[] min_to_end = new int[array.length];
    for (int i = array.length - 2; i >= 0; --i) {
        if (array[i] <= 0)
            min_to_end[i] = Integer.MAX_VALUE;
        else {
            int minimum = Integer.MAX_VALUE;
            for (int k = 1; k <= array[i]; ++k) {
                if (i + k < array.length)
                    minimum = Math.min(min_to_end[i+k], minimum);
                else
                    break;
            }
            min_to_end[i] = minimum + 1;
        }
    }
    return min_to_end[0];
} 

回答by Vasilescu Andrei

Years late to the party , but here is another O(n) solution that made sense for me.

聚会晚了几年，但这是另一个对我有意义的 O(n) 解决方案。

/// <summary>
/// 
/// The actual problem is if it's worth not to jump to the rightmost in order to land on a value that pushes us further than if we jumped on the rightmost.
/// 
/// However , if we approach the problem from the end,  we go end to start,always jumping to the leftmost
/// 
/// with this approach , these is no point in not jumping to the leftmost from end to start , because leftmost will always be the index that has the leftmost leftmost :) , so always choosing leftmost is the fastest way to reach start
/// 
/// </summary>
/// <param name="arr"></param>
static void Jumps (int[] arr)
{
    var LeftMostReacher = new int[arr.Length];
    //let's see , for each element , how far back can it be reached from 

    LeftMostReacher[0] = -1; //the leftmost reacher of 0 is -1

    var unReachableIndex = 1; //this is the first index that hasn't been reached by anyone yet
    //we use this unReachableIndex var so each index's leftmost reacher is  the first that was able to jump to it . Once flagged by the first reacher , new reachers can't be the leftmost anymore so they check starting from unReachableIndex

    // this design insures that the inner loop never flags the same index twice , so the runtime of these two loops together is O(n)

    for (int i = 0; i < arr.Length; i++)
    {
        int maxReach = i + arr[i];

        for (; unReachableIndex <= maxReach && unReachableIndex < arr.Length; unReachableIndex++)
        {

            LeftMostReacher[unReachableIndex] = i;
        }

    }

    // we just go back from the end and then reverse the path

    int index = LeftMostReacher.Length - 1;
    var st = new Stack<int>();

    while (index != -1)
    {
        st.Push(index);
        index = LeftMostReacher[index];
    }

    while (st.Count != 0)
    {
        Console.Write(arr[st.Pop()] + "  ");
    }
    Console.WriteLine();
}
static void Main ()
{
    var nrs = new[] { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
    Jumps(nrs);
}

回答by Sid Ray

Here is the basic intuition regarding the above problem's greedy approach and rest are the code requirements.

这是关于上述问题的贪婪方法的基本直觉，其余的是代码要求。

Given array is Input: a[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}.

给定数组是输入：a[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}。

Now we start from the 1st element i.e i=0 and a[i] = 1. So seeing this we can take at most a jump of size 1, so since we don't have any other choice so we make this step happen.

现在我们从第一个元素开始，即 i=0 和 a[i] = 1。所以看到这一点，我们最多可以进行大小为 1 的跳跃，因为我们没有任何其他选择，所以我们进行了这一步。

Currently we are at i=1 and a[i]=3. So we currently can make a jump of size 3, but instead we consider all possible jumps we can make from the current location and attain the maximum distance which is within bounds(of the array). So what are our choices? we can make a jump of 1 step, or 2 steps or 3 steps. So we investigate from current location for each size jumps and choose the one which can take us maximum further into the array.

目前我们处于 i=1 和 a[i]=3。因此，我们目前可以进行大小为 3 的跳转，但是我们考虑从当前位置可以进行的所有可能跳转，并获得在（数组的）边界内的最大距离。那么我们的选择是什么？我们可以跳 1 步，或 2 步或 3 步。因此，我们从当前位置调查每个大小的跳跃，并选择可以让我们最大程度地进一步进入数组的那个。

Once we have decided, which one we stick to, we take that jump size and update our number of jumps made so far and also where we can reach at most and how many steps we have now to decide our next move. And that's it. This is how finally we select the best option linearly traversing the array. So this is the basic idea of the algo you might be looking for, next is to code it for the algorithm to work. Cheers!

一旦我们决定了我们坚持哪一个，我们就会采用该跳跃大小并更新我们迄今为止所做的跳跃次数以及我们最多可以到达的位置以及我们现在需要多少步来决定下一步行动。就是这样。这就是我们最终选择线性遍历数组的最佳选项的方式。所以这是您可能正在寻找的算法的基本思想，接下来是对其进行编码以使算法工作。干杯!

Hope somebody time travels and finds the intuition helpful !! :) :P "Years late to the party" @Vasilescu Andrei - well said. Sometimes it feels to me that we are time travelers.

希望有人穿越时空，发现直觉有帮助！！:) :P “派对晚了几年”@Vasilescu Andrei - 说得好。有时我觉得我们是时间旅行者。

回答by kraskevich

Here is another linear solution. The code is longer than the one suggested in the leet code link, but I think it is easier to understand. It is based on a two observations: the number of steps required to reach the i + 1position is never less than the number of steps required to reach the iposition and each element each element assigns its value + 1 to i + 1 ... i + a[i]segment.

这是另一个线性解决方案。代码比leet代码链接中建议的要长，但我认为它更容易理解。它基于两个观察结果：到达该i + 1位置所需的步数永远不会少于到达该i位置所需的步数，并且每个元素的每个元素都将其值 + 1 分配给i + 1 ... i + a[i]分段。

public class Solution {
    public int jump(int[] a) {
        int n = a.length;
        // count[i] is the number of "open" segments with value i
        int[] count = new int[n];
        // the number of steps to reach the i-th position
        int[] dp = new int[n];
        Arrays.fill(dp, n);
        // toDelete[i] is the list of values of segments 
        // that close in the i-th position
        ArrayList<Integer>[] toDelete = new ArrayList[n];
        for (int i = 0; i < n; i++)
            toDelete[i] = new ArrayList<>();
        // Initially, the value is 0(for the first element).
        toDelete[0].add(0);
        int min = 0;
        count[0]++;
        for (int i = 0; i < n; i++) {
            // Finds the new minimum. It uses the fact that it cannot decrease. 
            while (min < n && count[min] == 0)
                min++;
            // If min == n, then there is no path. So we can stop.
            if (min == n)
                break;
            dp[i] = min;
            if (dp[i] + 1 < n) {
                // Creates a new segment from i + 1 to i + a[i] with dp[i] + 1 value
                count[dp[i] + 1]++;
                if (i + a[i] < n)
                    toDelete[i + a[i]].add(dp[i] + 1);
            }
            // Processes closing segments in this position.
            for (int deleted : toDelete[i])
                count[deleted]--;
        }
        return dp[n - 1];
    }
}

Complexity analysis:

复杂度分析：

1. The total number of elements in toDeletelists is O(n). It is the case because at each position iat most one element is added. That's why processing all elements in all toDeletelists requires linear time.

2. The minvalue can only increase. That's why the inner whileloop makes at most niterations in total.

3. The outer forloop obviously makes niterations. Thus, the time complexity is linear.

1. toDelete列表中的元素总数是O(n)。这是因为在每个位置i最多添加一个元素。这就是为什么处理所有toDelete列表中的所有元素需要线性时间。

2. 该min值只能增加。这就是内while循环n总共进行最多迭代的原因。

3. 外for循环显然进行n迭代。因此，时间复杂度是线性的。

回答by Amelio Vazquez-Reina

Many of the answers here so far are great, but I feel I can help explain whythe algorithm is correct and the intuition behind it.

到目前为止，这里的许多答案都很棒，但我觉得我可以帮助解释为什么算法是正确的以及它背后的直觉。

I like this problem because it's one where the intuitive dynamic programmingapproach runs in O(n^2)worst-case, and a greedy approach(the one that motivated this question) runs in O(n)worst-case (it actually only visits each element of the array once). This algorithm is also for me somewhat reminiscent of Dijkstra's algorithm which solves another single-source shortest-path problem and that is also greedy.

我喜欢这个问题，因为它是直观动态编程方法在O(n^2)最坏情况下运行的问题，而贪婪方法（激发这个问题的方法）在 O(n)最坏情况下运行（它实际上只访问数组的每个元素一次）。这个算法对我来说也有点让人想起 Dijkstra 的算法，它解决了另一个单源最短路径问题，这也是贪婪的。

To start, remember from the problem statement that A[i]holds the maximum position you can jump to from that index, but you cantake a shorter jumpfrom iif A[i]>1, so a shortest sequence of jumps from i=0could be one with shorter jumpsthan what's allowed on each index. This is important, since you will see that the algorithm never considers those smaller jumps or their locations explicitly.

首先，请记住问题陈述中A[i]包含您可以从该索引跳转到的最大位置，但是您可以从if进行更短的跳转，因此最短的跳转序列可能是比每个索引允许的跳转更短的跳转序列. 这很重要，因为您将看到该算法从不明确考虑那些较小的跳跃或其位置。iA[i]>1i=0

Second, it helps to think of the algorithm that you mentioned as one that gives itself "strands of rope" (steps = maxReach - i;) to reach the end, and that it consumes this rope (steps--;) as it tries to advance through the array.

其次，将您提到的算法视为一种算法，该算法为自己提供“绳索” ( steps = maxReach - i;) 以到达终点，并steps--;在它试图通过数组前进时消耗这根绳索 ( )。

Third, note that the algorithm is notkeeping track of the specific indices ithat may be part of ashortestsequence from the beginning to the end of the input array A. In fact, the algorithm only increases the variable jump(it gives itself a new strand of rope) when it "runs out of rope" (from the previous strand), so that it can keep iterating in the main loop to "try" to reach the end.

第三，注意，该算法是不跟踪的特定索引的i可能的部分一最短从开始到输入数组的末尾序列A。事实上，算法只jump在它“用完绳子”（来自前一绳）时才增加变量（它给自己一根新绳），这样它就可以在主循环中不断迭代以“尝试”到达结束。

More specifically for the algorithm to be correct it needs to:

更具体地说，为了使算法正确，它需要：

1. Keep trackof "how far it can reach" (maxReach) from each location ias it moves forward through the array. Note that this quantity is updated for each location evenif it's clear already at that moment that reaching that new location willrequireit to take more "jumps" as you exceed the number of steps (i.e. you run out of rope) that you gave yourself earlier, evenif no shortest path would actually visit that element. The goal of these updates is to identify how far the next jump could reach so that it can give itself that much rope once it exhausted the current one.

2. Accountfor the minimumnumber of jumps(jumps) you musttake if you want to continue iterating through the array to reach the end, as you run out of rope (steps) from the previous strand.

1. 当它向前移动穿过阵列时，跟踪maxReach每个位置的“它可以到达多远”（）i。请注意，此数量会针对每个位置进行更新，即使当时已经很清楚到达该新位置将需要它进行更多“跳跃”，因为您超过了给自己的步数（即绳子用完）更早一点，即使没有最短路径实际访问该元素。这些更新的目标是确定下一次跳跃可以达到多远，以便它在用完当前跳跃后可以给自己那么多绳索。

2. 帐户的最低数量的跳跃（jumps），你必须，如果你想继续迭代通过数组坚持到了最后，因为你的绳索（中跑出来取steps）从以前的链。

---

---

The algorithm that you linked to, for reference:

您链接到的算法，以供参考：

public class Solution {
    public int jump(int[] A) {
        if (A.length <= 1)
            return 0;
        int maxReach = A[0];
        int step = A[0];
        int jump = 1;
        for (int i = 1; i < A.length; i++) {
            if (i == A.length - 1)
                return jump;
            if (i + A[i] > maxReach)
                maxReach = i + A[i];
            step--;
            if (step == 0) {
                jump++;
                step = maxReach - i;
            }
        }
        return jump;
    }
}

回答by fight_club

Okay, it took me good amount of time to wrap my head around the O(n) algo, I will try to explain the logic to my best simplest possible:

好的，我花了很多时间来理解 O(n) 算法，我将尝试用最简单的方式解释逻辑：

At each "i" in the array, you know with that value what is the currentFarthest value, you can reach up to, & also the currentEnd value, whenever you hit the currentEnd value, you know its time to make a jump & update currentEnd with currentFarthest.

在数组中的每个“i”处，您知道该值是什么 currentFarthest 值，您可以达到，以及 currentEnd 值，每当您达到 currentEnd 值时，您就知道是时候进行跳转和更新 currentEnd与 currentFarthest。

The picture below might help :

下面的图片可能会有所帮助：

回答by Ishaan Sharma

I have done this with Python. Less complex code with simple terms. This might help you.

我已经用 Python 做到了这一点。使用简单术语的不太复杂的代码。这可能对你有帮助。

def minJump(a):
    end=len(a)
    count=0
    i=a[0]
    tempList1=a
    while(i<=end):
        if(i==0):
            return 0
        tempList1=a[count+1:count+i+1]
        max_index=a.index(max(tempList1))
        count+=1
        i=a[max_index]
        end=end-max_index
    return count+1

回答by Vishwanath Hiremath

Simple python code for the Minimum number of jumps to reach end problem.

用于到达终点问题的最小跳转次数的简单 python 代码。

ar=[1, 3, 6, 3, 2, 3, 6, 8, 9, 5]
minJumpIdx=0
res=[0]*len(ar)
i=1
while(i<len(ar) and i>minJumpIdx):
    if minJumpIdx+ar[minJumpIdx]>=i:
        res[i]=res[minJumpIdx]+1
        i+=1
    else:
        minJumpIdx+=1
if res[-1]==0:
    print(-1)
else:
    print(res[-1])

回答by Sanjeev Kumar

static void minJumps(int a[] , int n)
{
    int dp[] = new int[n];
    dp[0] = 0;  //As the min jumps needed to get to first index is zero only.
    //Fill the rest of the array with INT_MAX val so we can make math.min comparisions.
    for(int i=1;i<n;i++)
        dp[i] = Integer.MAX_VALUE;

    for(int i=1;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {   //If we have enough jumps from the position j to reach i. 
            if(j+a[j]>=i)    
            {   //Take the min of current stored value & jumps req to 
              //reach i from j by getting jumps req to reach j plus 1.
              //(Plus 1 because since we have enough jumps to reach 1 from j we 
              //simply add 1 by taking the jumps required to reach j.)
                dp[i] = Math.min(dp[i],dp[j]+1);
            }
        }
    }

    //If first element has zero jumps in store or if the final jumps value 
    //becomes MAX value because there's an element in between which gives zero
    //jumps.
    if(a[0]==0 || dp[n-1] == Integer.MAX_VALUE ) 
    System.out.println("-1");

    else System.out.println(dp[n-1]);
}