【转】分治法求最大值最小值
分治算法通俗的讲就是把一个规模比较大的问题分成n个规模较小的问题来解决，再将每个小规模的问题进行合并，最后得到结果。通常问题规模比较大难以用普通的编程方法实现，或者不可能实现的时候采用分治算法，能够简化问题的解决。
一个例子：
求出一个数组中的最大值和最小值。
package example;
public class MaxAndMinValue {
// 直接算法 得到最大值和最小值
public static void main(String[] args) {
int[] A = { -18, -16, 9, -5, 7, -40, 0, 35 };
System.out.println(getMaxValue(A));
System.out.println(getMinValue(A));
System.out.println(getMax(A, 0, A.length - 1));
}
// 直接算法求最大值
public static int getMaxValue(int[] array) {
int Max = 0;
for (int i = 0; i < (array.length - 1); i++) {
if (array[i] == array[i + 1]) {
Max = array[i + 1];
}
if (array[i] < array[i + 1]) {
Max = array[i + 1];
}
if (array[i] > array[i + 1]) {
Max = array[i];
array[i] = array[i + 1];
array[i + 1] = Max;
}
}
return Max;
}
// 直接算法求最小值
public static int getMinValue(int[] array) {
int Min = 0;
for (int i = 0; i < (array.length - 1); i++) {
if (array[i] == array[i + 1]) {
Min = array[i + 1];
} else if (array[i] < array[i + 1]) {
Min = array[i];
array[i] = array[i + 1];
array[i + 1] = Min;
} else if (array[i] > array[i + 1]) {
Min = array[i + 1];
}
}
return Min;
}
// 用分治法求最大最小值
public static int getMax(int[] array, int i, int j) {
int Max1 = 0;
int Max2 = 0;
if (i == j) {
return Max1 = Max2 = array[j];
} else if (i == (j - 1)) {
Max1 = array[i];
Max2 = array[j];
return Max1 > Max2 ? Max1 : Max2;
} else {
int mid = (i + j) / 2;
Max1 = getMax(array, i, mid);
Max2 = getMax(array, mid, j);
return Max1 > Max2 ? Max1 : Max2;
}
}
}
假设数组的大小为8，用直接的算法，最大值最小值总需要比较14次，而用分治算法可以一次性求出最大和最小，只需要10次比较。
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。