最小阵列值使用递归不正确

Question

我正在尝试创建一种使用递归搜索最小值的1D数组的方法。它确实给了我一个输出，但是无论阵列是否包含" 1"，它总是" 1"。我对编程非常陌生，并感谢任何帮助。

public static int smallest(int[] array)
{
    return smallestFrom(array, 0);
}
static int min = 500; //large number
private static int smallestFrom(int[] array, int i)
{ 
    int x = array.length;
    if (i < x && array[i] < min)
    {
        min = array[i];
        i++;
        smallestFrom(array, i);
    }
    else if (i < x && array[i] >= min)
    {
        i++;
        smallestFrom(array, i);
    }
    return min;
}

输出：

2,4,6,1,6,3,8
Smallest: 1
43,76,3,23,95,23
Smallest: 1

Answer 1

您的实现对我来说很好。好吧，这说得太多了，但是有效。但是您可以改进很多：

大整数

为什么将一些任意号码用作"大数字"？该代码将破坏值大于500的输入。您应该只使用常数Integer.MAX_VALUE。没有比这个值更大的值，它是在清晰的庄园中命名的，它是由API定义的。

全局变量

这是发生错误的地方。您的实现是为单次使用设计的。使用第一个数组运行后，min将保持1。由于在第二个示例阵列中没有大于1的数字，因此它将再次返回1。可以通过将min重置为每次smallest的原始值来修复，或者完全放弃它（见下文）。

分支

这个问题可以通过更少的条件来解决。我们可以使用最大数组的最大定义，而不是存储最小值：

max({a, b, c, d, e, f}) = max({a, max({b, c, d, e, f})})

看起来更复杂？实际上不是。这个想法是，数组的最大值是其第一个元素的最大值，也是数组中所有剩余元素的最大值。现在可以将其翻译成更简单的代码。

将它们全部放在一起

static int min(int[] arr)
{
    return minRec(arr, 0);
}
static int minRec(int[] arr, int i)
{
    if(i == arr.length)
        return Integer.MAX_VALUE;
    return Math.min(arr[i], minRec(arr, i + 1));
}

看起来很整洁，不是吗？Math.min(int, int)只是返回两个参数的函数的api implentation。