简明现代魔法 -> 计算机算法 -> 用分治法求数组中的最大最小值

用分治法求数组中的最大最小值

2010-10-26

分治算法通俗的讲就是把一个规模比较大的问题分成n个规模较小的问题来解决,再将每个小规模的问题进行合并,最后得到结果。通常问题规模比较大难以用普通的编程方法实现,或者不可能实现的时候采用分治算法,能够简化问题的解决。

下面举个例子,求出一个数组中的最大值和最小值。

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次比较。

随机文章推荐
网站分类


注:如需转载本文,请注明出处(原文链接),谢谢。更多精彩内容,请进入简明现代魔法首页。

进入新博客
喜欢本文,就分享它吧
给我留言
您的名字:
您的邮件:
您的网站:


 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们