java - 使用递归时最小数组值不正确

Question

我正在尝试创建一种方法来使用递归搜索一维数组的最小值。它确实给了我一个输出，但无论数组是否包含“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。可以通过每次调用 smallest 时将 min 重置为原始值，或者完全放弃它(见下文)来解决此问题。

分支

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

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 实现。