算法之分治 - 求解最大值和最小值

104 阅读 0 评论 69 点赞

我是靠谱客的博主老实海燕，最近开发中收集的这篇文章主要介绍算法之分治 - 求解最大值和最小值，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

顾名思义，“分治”名字本身就已经给出了一种强有力的算法设计技术，它可以用来解决各类问题。在它最简单的形式里，一个分治算法把问题实例划分成若干子实例（多数情况是分成两个），并分别递归地解决每个子实例，然后把这些子实例的解组合起来，得到原问题实例的解。

为了阐明这个方法，考虑这样一个问题：在一个整数组A[1...n]中，同时寻找最大值和最小值。为了简化问题，不妨假定n是2的整数幂。一中直接的算法如下面所示，它返回一个数对（x，y），其中x是最小值，y是最大值：

x ← A[1]; y ← A[1]

for i ← 2 to n

if A[i] < x then x ← A[i]

if A[i] > y then y ← A[i]

end for

return (x,y)

显然，由以上方法执行的元素比较次数是2n-2。

下面我们来看一下用分治策略：将数组分割成两半，A[1...n/2]和A[(n/2)+1...n]，在每一半中找到最大值和最小值，并返回这两个最小值中的最小值及这两个最大值的最大值。

过程 Min-Max

输入 n个整数元素的数组A[1...n]，n为2的幂

输出 (x,y), A中的最大元素和最小元素

算法描述 minmax(low, high)

if high - low = 1 then

if A[low] < A[high] then return (A[low], A[high])

else return (A[high], A[low])

end if

else

mid ← ⌊(low + high)/2⌋

(x1, y1 ) ← minmax(low, mid)

(x2, y2 ) ← minmax(mid + 1, high)

x ← min { x1, x2 }

y ← min { y1, y2 }

return (x, y)

end if

这个算法要注意一点，我们已经假定n是2的整数幂。不然的话，算法里面的递归调用会进入死循环...

下面是此算法的Java实现：

Pairs.java 这个类用来保存最大值和最小值：

public class Pairs
{
private int minValue;
private int maxValue;
public Pairs(int minValue, int maxValue)
{
this.minValue = minValue;
this.maxValue = maxValue;
}
public static Pairs valueOf(int minValue, int maxValue)
{
return new Pairs(minValue, maxValue);
}
public int getMaxValue()
{
return maxValue;
}
public int getMinValue()
{
return minValue;
}
}

DivideAndConquer.java 包含实现 Min-max 算法的类：

public class DivideAndConquer
{
public static Pairs minMax(int[] array, int low, int high)
{
if (high - low == 1)
{
int minValue = Math.min(array[low], array[high]);
int maxValue = Math.max(array[low], array[high]);
return Pairs.valueOf(minValue, maxValue);
}
int middle = (low + high) / 2;
Pairs pairs1 = minMax(array, low, middle);
Pairs pairs2 = minMax(array, middle + 1, high);
return Pairs.valueOf(Math.min(pairs1.getMinValue(), pairs2.getMinValue()),
Math.max(pairs1.getMaxValue(), pairs2.getMaxValue()));
}
}

Program.java 包含程序的入口方法，这里面还对传入的数组进行了判断，是否为null或者数组长度为2的幂：

当然也可以不用设置low=0, high=array.length - 1，只要 (high - low + 1) 是2的幂就可以了

public class Program
{
public static void main(String[] args)
{
int[] array = new int[] { 332, 566, 51, 70, 98, 19, 24, 637,
53456, 3321, -235, -34, 5, 45, 77, 36 };
if (array == null || !isValidPower(array.length))
{
System.err.println("Invalid Array!");
return;
}
Pairs pairs = DivideAndConquer.minMax(array, 0, array.length - 1);
String message = String.format("Min Value: %dnMax Value: %d",
pairs.getMinValue(), pairs.getMaxValue());
System.out.println(message);
}
// 这个方法判断传入的参数是否为2的幂（不包括0和负数）
private static boolean isValidPower(int power)
{
if (power < 2)
return false;
while (power >= 2)
{
if (power % 2 != 0)
return false;
power /= 2;
}
return true;
}
}