參考資料：https://programmerall.com/article/3518233476/
public class Test {
public static void main(String[] args) {
//Divide and conquer分治法
//取出陣列中的最大與次大值
//做法：先將陣列分兩堆取出各自的最大與次大：lo->mid/ mid+1->hi
//兩兩最大比較，其中一個勝出為最終最大，另一個最大與另一堆的次大比較，其中一個勝出為最終次大
//1.取最大與次大，所以陣列元素最少要有兩個
//2.所以陣列中若只有一個元素，則次大值設定預設值
int[] array = new int[]{3,5,67,43,54};
int lo = 0, hi = array.length-1;
int[] retMax2 = findMax2(array, lo, hi);
System.out.println("max1="+retMax2[0]+",max2="+retMax2[1]);
}
public static int[] findMax2(int[] array, int lo, int hi) {
int max1 = 0, max2 = 0;
int[] retMax = new int[2];
int mid = (lo + hi) / 2;
int inf = -9999;
if (lo == hi) {// 陣列中只有一個元素
max1 = array[lo];
max2 = inf;
} else if (lo + 1 == hi) {// 陣列中有兩個元素
max1 = Math.max(array[lo], array[hi]);
max2 = Math.min(array[lo], array[hi]);
} else {
int[] maxL = findMax2(array, lo, mid);
int[] maxR = findMax2(array, mid + 1, hi);
if (maxL[0] > maxR[0]) {
max1 = maxL[0];
max2 = Math.max(maxL[1], maxR[0]);
} else {
max1 = maxR[0];
max2 = Math.max(maxR[1], maxL[0]);
}
}
retMax[0] = max1;
retMax[1] = max2;
return retMax;
}
}
如有敘述錯誤，還請不吝嗇留言指教，thanks!