arrays - 检查数组中最小跳转次数算法的正确性

Question

我有一个算法是基于一个问题，你需要找到到达数组末尾的最小跳跃次数。这个问题是在极客中问到极客的，他们在我的中没有线性时间算法如果算法在线性时间内，但我的算法会在哪个测试用例中失败？。问题的链接

链接:- http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/

输入:arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}

• 从第一个元素开始，我们知道该元素的最大范围是 1，因此我们只能向前移动一步，所以从 1->3

• 现在在第二步中我们知道元素的范围是 3，因此从这一步我们计算该范围的最大值，因此我们可以从 3 中选择 5、8、9 并且该范围内的最大值是9

• 所以首先移动到 9，即 1->3->9，然后我们从 9 移动到数组的末尾，因为我们知道九步足以到达末尾。

• 极端情况是，如果我们在末尾检测到零，则我们什么都不做，因为我们已经到达末尾。但是如果在开始处或在 0 是其中最大元素的范围内检测到零向前移动的范围我们返回 -1，因为我们无法进一步移动如果此算法中存在错误，请告诉我。

Answer 1

是的，这个算法行不通。示例:

arr[] = {5,2,1,1,1,1,1}

您的算法会看到 5，然后看到最大数字 2，然后转到 1 1 1 1。即:5,2,1,1,1,1 = 6 次跳跃。

虽然最佳结果是:5 -> 1(倒数第二个)-> 1 = 3 跳