java - 使用分而治之的方法找到最大值和最小值

Question

我知道这是一个愚蠢的问题，但我根本不明白。这段代码取自 http://somnathkayal.blogspot.in/2012/08/finding-maximum-and-minimum-using.html

public int[] maxMin(int[] a,int i,int j,int max,int min) {
    int mid,max1,min1;
    int result[] = new int[2];

    //Small(P)
    if (i==j) max = min = a[i];
    else if (i==j-1) { // Another case of Small(P)
        if (a[i] < a[j]) {
            this.max = getMax(this.max,a[j]);
            this.min = getMin(this.min,a[i]); 
        }
        else {
            this.max = getMax(this.max,a[i]); 
            this.min = getMin(this.min,a[j]); }
        } else {
            // if P is not small, divide P into sub-problems.
            // Find where to split the set.

            mid = (i + j) / 2;
            // Solve the sub-problems.
            max1 = min1 = a[mid+1];
            maxMin( a, i, mid, max, min );    
            maxMin( a, mid+1, j, max1, min1 );

            // Combine the solutions.
            if (this.max < max1) this.max = max1;
            if (this.min > min1) this.min = min1;
        }

        result[0] = this.max;
        result[1] = this.min;
        return result;
    }
}

假设数组是 8,5,3,7 我们必须找到最大值和最小值，max和min的初始值=arr[0]=8；第一次名单将分为8,5我们用 max=8 和 min=8 调用 MaxMin，因为 i==j-1，我们将得到 max=8，min=5，

下次列表将分为[3,7],min1=max1=arr[mid+1]=3,我们用 max=3 和 min=3 调用 MaxMin。由于 i 等于 j-1，我们将得到 max=7,min=3,

接下来比较 max1,max 和 min1,min ,这是我的困惑，这里的max和max1的值分别是8和7，但是怎么办？？？我们哪里都没有修改max1，那么它的值怎么会是7呢，

根据我的理解，我们调用了 MaxMin，max=3 和 min=3，然后更新了 max=7 和 min=3，但是我们没有返回这些更新的值，那么 max1 和 min1 的值是如何更新的,我被困在这，请解释。谢谢。

Answer 1

看起来你正在更新 2 个外部值(不在这个函数中)，它们是 this.min 和 this.max

您所做的只是将 1 或 2 个元素分成多个部分，然后更新 this.min 和 this.max，因此您也可以直接扫描数组并检查所有 int 值的最小值/最大值。这并不是真正的分而治之。

这是一个真正使用分而治之的解决方案:

public int[] maxMin(int[] a,int i,int j) {
    int localmin,localmax;
    int mid,max1,min1,max2,min2;
    int[] result = new int[2];

    //Small(P) when P is one element
    if (i==j) {
        localmin = a[i]
        localmax = a[i];
    }
    else {
        // if P is not small, divide P into sub-problems.
        // where to split the set
        mid = (i + j) / 2;
        // Solve the sub-problems.
        int[] result1 = maxMin( a, i, mid);    
        int[] result2 = maxMin( a, mid+1, j);
        max1 = result1[0];
        min1 = result1[1];
        max2=result2[0];
        min2=result2[1];
        // Combine the solutions.
        if (max1 < max2) localmax = max2;
        else localmax=max1;
        if (min1 < min2) localmin = min1;
        else localmin=min2;
    }

    result[0] = localmax;
    result[1] = localmin;
    return result;
}