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

Question

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)

从 Dynamic Programming approach 找到了多种方式到其他线性方法。我无法理解所谓的时间线性方法。 HERE是提出线性方法的链接。

我完全看不懂。我能理解的是，作者建议采用贪婪的方法，看看我们是否到达终点……如果没有，则回溯？

Answer 1

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

变量 maxReach 始终存储数组中的最大可达位置。 jump 存储到达该位置所需的跳跃次数。 step 存储我们仍然可以走的步数(并在第一个数组位置用步数初始化)

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

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

接下来我们更新最大可达位置。这等于 maxReach 和 i+A[i] 的最大值(我们从当前位置可以采取的步数)。

我们用了一步到达当前索引，因此必须减少 steps。

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

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;
    }
}

例子:

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.

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

代码

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];
}