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

Question

该函数仅获取 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

Answer 1

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

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+1 次，因此它是线性的，就像 for 循环