时间戳

首页 > 解决方案 > 递归查找并返回数组中的最小值和最大值

java - 递归查找并返回数组中的最小值和最大值

问题描述

该函数仅获取 2 个参数：数字的 arr 和 n 表示它们在数组中的数量。我需要递归查找并返回数组中的最小值和最大值。以3n/2比较 的最小复杂度。下面的代码仅返回 MIN。我应该如何使它返回 MIN 和 MAX？

public class MyClass {

    public static void main(String[] args) {

        int A[] = { 1, 4, 45, 6, -50, 10, 2 };
        int n = A.length;

        // Function calling
        System.out.println(findMinMaxRec(A, n));

    }

    public static int findMinMaxRec(int A[], int n) {
        // if size = 0 means whole array
        // has been traversed
        if (n == 1)
            return A[0];

        for (int i = 0; i < n; i++)
            return Math.min(A[n - 1], findMinMaxRec(A, n - 1));

        // The program NO return min and max (both)
        return Math.max(A[n - 1], findMinMaxRec(A, n - 1));
    }
}

答案：

-50
45

标签： java

解决方案

两个版本，一个按升序排列，一个按降序排列：

static int[] findMinMaxRecDesc(int[] A, int n) {
    if (n == 0) {
        return new int[]{A[0], A[0]};
    }
    int[] recResult = findMinMaxRecDesc(A, n - 1);
    return new int[]{Math.min(A[n - 1], recResult[0]), Math.max(A[n - 1], recResult[1])};
}

static int[] findMinMaxRecAsc(int[] A, int n) {
    if (n == A.length - 1) {
        return new int[]{A[n], A[n]};
    }
    int[] recResult = findMinMaxRecAsc(A, n + 1);
    return new int[]{Math.min(A[n], recResult[0]), Math.max(A[n], recResult[1])};
}


public static void main(String[] args) {
    int[] array = {1, 4, 45, 6, -50, 10, 2};
    int[] result = Arrays.toString(findMinMaxRecAsc(array, array.length))
    System.out.println(result); // [-50, 45]
}

并且该方法findMinMaxRec被称为n+1times，所以它是线性的，就像一个for循环

推荐阅读