java 我如何找到一个递归数组的最大值而没有索引?

db2dz4w8  于 2022-10-30  发布在  Java
关注(0)|答案(2)|浏览(152)

我有一个valorMaxim([1, 5, 252, 24, 7, 82, 3])返回252的方法,我不知道怎么做,我一直在想,如果我可以减少数组长度。

public static int valorMaxim(int arr[]){
    int max;

    if(arr.length==1)
        return arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] < arr[i+1]) {
            max=arr[i+1];
            return arr[i+1];
        }
    }
    return valorMaxim(arr);

    //Retorna el valor màxim en un array no buit d’enters.
}
e0bqpujr

e0bqpujr1#

我将接受的答案修改为Finding Max value in an array using recursion
按照您的建议(即每次调用递归方法时减少数组长度),我创建了一个长度比参数小1的方法参数副本,并删除了第一个元素,然后用数组副本递归调用方法。

public class Main {

    public static int valorMaxim(int arr[]){
        if (arr.length == 1) {
            return arr[0];
        }
        else {
            int[] tmp = new int[arr.length - 1];
            System.arraycopy(arr, 1, tmp, 0, tmp.length);
            return Math.max(arr[0], valorMaxim(tmp));
        }
    }

    public static void main(String[] args) {
        System.out.println(valorMaxim(new int[]{1, 5, 252, 24, 7, 82, 3}));
    }
}
bpsygsoo

bpsygsoo2#

基本上,递归的思想是:
1.如果数组长度为1,则返回唯一的元素;
1.否则,将数组拆分为x(第一个元素)和xs(其余元素);
1.找出xs中最大的元素,将其与x比较,得出较大的值。
有两种方法可以实现这样的“分裂”:
1.为xs创建部分数组的新副本
您可以使用System.arraycopy(请参阅@Abra的答案)或Arrays.copyOfRange,后者更简单:

int x = arr[0];
int[] xs = Arrays.copyOfRange(arr, 1, arr.length);

现在,我们查找xs中的最大元素(即valorMaxim(xs)),并将其与x进行比较,作为最终结果:

return Math.max(x, valorMaxim(xs));

将所有内容放在一起,不要忘记添加一个长度检查器:

public static int valorMaxim(int arr[])
{
    if (arr.length == 1) return arr[0];

    int x = arr[0];
    int[] xs = Arrays.copyOfRange(arr, 1, arr.length);

    return Math.max(x, valorMaxim(xs));
}

就是这样!因为我们首先有长度检查器,我们可以安全地确保xs永远不会为空,因此valorMaxim(xs)永远不会得到ArrayIndexOutOfBoundsException
1.设定数组的边界
你可能已经发现,每次复制一个新的数组可能会消耗大量的时间和内存。与其为xs创建一个物理副本,我们可以将这个想法概念化,并使用一个有界数组来代替。我们需要定义一个helper方法来实现这一点:

private static int findMaxBound(int arr[], int startFrom)
{
    // does "xs" have length 1?
    if (startFrom == arr.length - 1) return arr[startFrom];

    int x = arr[startFrom];
    int maxInXs = findMaxBound(arr, startFrom + 1);

    return Math.max(x, maxInXs);
}

然后我们可以将valorMaxim定义为

public static int valorMaxim(int arr[])
{
    return findMaxBound(arr, 0);
}

最后,我们没有创建arr的任何新副本,而是使用其自身的不同范围,并在整个过程中将它们视为xs

相关问题