arrays - 使用递归查找数组中的最大元素

Question

我是一个算法初学者，刚想出了一个“递归求整数数组中的最大元素”的解决方案:

public static int findMax(int[]arr)
{

  if(arr.length==1)
    return arr[0];

  return findMax(Arrays.copyOf(arr, arr.length-1))> arr[arr.length-1]?findMax(Arrays.copyOf(arr, arr.length-1)):arr[arr.length-1];
}

我确实测试了几次，它似乎工作正常。

但是，我发现有人使用其他递归方法解决了这个问题，就像这篇文章一样:

finding max value in an array using recursion java

他的代码是这样的:

 int largest(int[] a, int start, int largest) 
 {
   if (start == a.length)
     return largest;
   else {
    int l = (a[start] > largest ? a[start] : largest);
    return largest(a, start + 1, l);
}

我在这里停留在我们对这个特定问题的思维方式差异的本质上。我的想法是这样的:

1.他在每次递归中使用另一个参数“start”来跟踪当前光标到数组元素，我没有使用它，因为我在每次递归中将数组缩小 1 并且总是使用尾元素来比较；

2.他使用另一个参数“largest”来跟踪目前找到的最大值。我没有在我的代码中使用这个，但我没有使用那个。这实际上是我陷入困境的地方。我没有使用那个“最大”变量来跟踪每次迭代中的最大值，为什么我可以获得相同的结果？

非常感谢任何帮助!

Answer 1

首先 n.m 说的是对的，复制数组是昂贵且不必要的。另一个算法使用 start 来避免这种情况。

但是对于你的问题。你实际上使用了 largest 只是没有给它命名!

return findMax(Arrays.copyOf(arr, arr.length-1))> arr[arr.length-1]?findMax(Arrays.copyOf(arr, arr.length-1)):arr[arr.length-1];

是您找到最大的地方。它与您提到的另一种算法完全一样。首先你找到最大的:findMax(Arrays.copyOf(arr, arr.length-1)) 然后你比较它的值:arr[arr.length-1] 选择较大的作为当前最大的。

另一个建议，为什么你需要调用 findMax(Arrays.copyOf(arr, arr.length-1)) 两次？只需使用一个变量来提高您的算法速度。