我知道这是一个愚蠢的问题，但我根本不明白。 这段代码取自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的值是如何更新的， 我被困在这个问题上，请解释一下。 谢谢。
看起来您正在更新 2 个外部值（不在这个函数中），即 this.min 和 this.max
您所做的就是分割成 1 或 2 个元素，然后更新 this.min 和 this.max，因此您也可以直接扫描数组并检查所有 int 值的 min/max。这并不是真正的分而治之。
这是一个真正使用分而治之的解决方案：
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;
}
坦白说，博主的代码看起来一团糟。你应该对此没有信心。
早先采取的是这条线：
if (i==j) max = min = a[i];
在这种情况下，传递给函数的值 max 和 min 不会被使用，它们只是被设置，然后就永远丢失了。另请注意，如果此行运行，则既不会设置也不会返回数组
result代码有时表现得像是通过
maxminresultthis.maxthis.min如果不运行它，我无法完全决定算法是否会返回错误的结果。它可能只是碰巧起作用。但它一团糟，如果写得更好，你就可以放心地看到它是如何工作的。我认为作者应该以更纯粹的函数式风格编写它，而不依赖像
this.minthis.max顺便说一句，我注意到当有人在评论中提出问题时，他回答说理解算法是主要目标。 “这个算法的实现非常复杂。我正在用这个为你更新一个程序。”哎呀，谢谢。
总之，找一个不同的例子来研究。 《黑暗之王》在我最初写这篇文章时发布了一条回复，看起来已经改进了很多。
代码
import java.util.Random;
public class MinMaxArray {
private static Random R = new Random();
public static void main(String[] args){
System.out.print("\nPress any key to continue.. ");
try{
System.in.read();
}
catch(Exception e){
;
}
int N = R.nextInt(10)+5;
int[] A = new int[N];
for(int i=0; i<N; i++){
int VAL = R.nextInt(200)-100;
A[i] = VAL;
}
Print(A);
Pair P = new Pair(Integer.MIN_VALUE, Integer.MAX_VALUE);
P = MinMax(A, 0, A.length-1);
System.out.println("\nMin: " + P.MIN);
System.out.println("\nMax: " + P.MAX);
}
private static Pair MinMax(int[] A, int start, int end) {
Pair P = new Pair(Integer.MIN_VALUE, Integer.MAX_VALUE);
Pair P_ = new Pair(Integer.MIN_VALUE, Integer.MAX_VALUE);
Pair F = new Pair(Integer.MIN_VALUE, Integer.MAX_VALUE);
if(start == end){
P.MIN = A[start];
P.MAX = A[start];
return P;
}
else if(start + 1 == end){
if(A[start] > A[end]){
P.MAX = A[start];
P.MIN = A[end];
}
else{
P.MAX = A[end];
P.MIN = A[start];
}
return P;
}
else{
int mid = (start + (end - start)/2);
P = MinMax(A, start, mid);
P_ = MinMax(A, (mid + 1), end);
if(P.MAX > P_.MAX){
F.MAX = P.MAX;
}
else{
F.MAX = P_.MAX;
}
if(P.MIN < P_.MIN){
F.MIN = P.MIN;
}
else{
F.MIN = P_.MIN;
}
return F;
}
}
private static void Print(int[] A) {
System.out.println();
for(int x: A){
System.out.print(x + " ");
}
System.out.println();
}
}
class Pair{
public int MIN, MAX;
public Pair(int MIN, int MAX){
this.MIN = MIN;
this.MAX = MAX;
}
}
解释
这是在 Pair 类的帮助下使用“分而治之”方法找出数组中的 MIN 和 MAX 值的 JAVA 代码。
JAVA 的Random 类 使用随机大小 N ε(5, 15) 和范围在 (-100, 100) 之间的随机值初始化数组。
创建了 Pair 类的对象 P，它从 MinMax() 方法取回返回值。 MinMax() 方法采用数组 (A[])、起始索引 (start) 和最终索引 (end) 作为参数。
工作逻辑
创建了 Pair 类的三个不同对象 P、P_、F。案例：-
更多代码链接
https://www.techiedelight.com/find-minimum-maximum-element-array-minimum-comparisons/ https://www.enjoyalgorithms.com/blog/find-the-minimum-and-maximum-value-in-an-array
public class MaxMinOptimal {
// Helper method to find max and min using divide and conquer
public static int[] findMaxMin(int[] arr, int low, int high) {
int maxElement, minElement;
// If there is only one element
if (low == high) {
maxElement = minElement = arr[low];
return new int[]{maxElement, minElement};
}
// If there are two elements
if (high == low + 1) {
if (arr[low] > arr[high]) {
maxElement = arr[low];
minElement = arr[high];
} else {
maxElement = arr[high];
minElement = arr[low];
}
return new int[]{maxElement, minElement};
}
// If there are more than two elements, split the array
int mid = (low + high) / 2;
int[] leftResult = findMaxMin(arr, low, mid);
int[] rightResult = findMaxMin(arr, mid + 1, high);
// Compare results from both halves
maxElement = Math.max(leftResult[0], rightResult[0]);
minElement = Math.min(leftResult[1], rightResult[1]);
return new int[]{maxElement, minElement};
}
public static void main(String[] args) {
int[] arr = {3, 5, 1, 2, 4, 8};
int[] result = findMaxMin(arr, 0, arr.length - 1);
System.out.println("Maximum: " + result[0]);
System.out.println("Minimum: " + result[1]);
}
}