用Java递归求数组的最小值和最大值

Question

class MinMax{
    public static Pair mmA(int lb, int ub, int[] a){
        int min;
        int max;
        int mid;
        if (ub == lb){
            return mmA(lb, ub, a);
        } else {
            mid = (lb + ub)/2;
            mmA (lb, mid, a);
            max = mid;
            mmA (mid+1, ub, a);
            min = mid;

            if (a[max] > a[min]){
                return mmA(lb, max, a);
            } else 
                return mmA(min, ub, a);
        }
    }

    public static void main(String[]args){
        int[] a = {4, 3, 5, 6, 7, 9, 1};
        mmA(0, 6, a);
    }
}

class Pair {
   int alpha;   // the smaller one 
   int omega; // the bigger one 
   Pair ( int a, int o ) { alpha = a; omega = o; }
}

那么我如何使用这个pair类和我的方法来找到最小值和最大值。

Answer 1

由于这似乎是递归中的一个练习，让我试着在这个借口下指导你们。

递归方法返回一对，即最小值和最大值。通过将数组一分为二来调用它两次。到目前为止一切都很好。

现在您有了两个对（假设您更改代码来实际为一个变量赋值），您只需要将它们组合起来。假设您的pair类是不可变的，那么您可以向pair添加一个方法，如下所示：

public Pair combine(Pair other) {
    int newAlpha = Math.min(this.alpha, other.alpha);
    int newOmega = Math.max(this.omega, other.omega);
    return new Pair(newAlpha, newOmega);
}