有趣的算法（十一） ——分治法：快速求最值
有趣的算法（十一）——分治法：快速求最值
（原创内容，转载请注明来源，谢谢）
一、需求
一个数组，里面有若干的数字，现需要得到这一组数字的最大值和最小值。
二、简单分析
最基本的做法，是两两比对，可以区分出临时的最大值和最小值，再拿临时的最大值和最小值往后比较，有新的最值则更新。总的需要的比较次数是2n-2。
三、优化
使用分治法快速求最值。即把数组分到最小的1-2个数，两两比较后，仅将最大值和最小值回传，再两两比较最值，回传新的最值，最终得出最大值和最小值。
分析需要比较的次数。当数组只有1个数时，T(1)=0；2个数时，T(2)=1。n个数字时，T(n)=2T(n/2)+2。
推导T(n)=2T(n/2)+2= 22T(n/22)+22+2…=2k-1T(2)+2k-1+2k-2+…22+2=2k-1+2k-2。
因此，当n=2k时，需要的次数是n/2+n-2=3n/2-2。当n不是2k，则次数会比3n/2-2略多，正好2的k次的数组长度时，这种算法较快。
四、实现
使用php编程，代码如下：
<?php
$x = 0;
//快速求最值-返回 array(min, max)
function quickMost(array $nums)
{
$len = count($nums);
if(1 == $len)
{
returnarray(reset($nums), reset($nums));
}
if(2 == $len)
{
$min =reset($nums);
$max =next($nums);
if($min >$max)
{
$tmp= $min;
$min= $max;
$max= $tmp;
}
$GLOBALS['x']++;
returnarray($min, $max);
}
$arr1 =array_slice($nums, floor($len/2));
$arr2 =array_diff($nums, $arr1);
list($min1, $max1) =quickMost($arr1);
list($min2, $max2) =quickMost($arr2);
$min = $min1 <=$min2 ? $min1 : $min2;
$GLOBALS['x']++;
$max = $max1 >=$max2 ? $max1 : $max2;
$GLOBALS['x']++;
return array($min,$max);
}
$testArr = array(7,8,5,1,4,9,0,3);
$res = quickMost($testArr);
var_dump($res);
echo $x;结果如下：
aarray(2) { [0]=> int(1) [1]=> int(9) }
10正确算出了最值，数字个数为8，则预测的比较次数为3n/2-2=3*8/2-2=10，和输出结果一致。
说明：
这里用到里一个php的array_diff，返回的是一个数组有的且另一个数组没有的数字，这样一定程度上如果有重复数字可以减少比较的次数。
但是，存在问题，当diff后，由于是返回一个差集，因此第二个数组可能是空树组的情况，例如输入的需要比较的数组为(1,1,1,1,1,1)，此时的$arr2会是空树组，则会报错。因此，需要在第二次递归调用quickMost方法时，进行一个判断，即可正确解决此问题。修改如下：
if(false == empty($arr2))
{
list($min2, $max2) =quickMost($arr2);
$min = $min <= $min2 ?$min : $min2;
$GLOBALS['x']++;
$max = $max >= $max2 ?$max : $max2;
$GLOBALS['x']++;
}——written by linhxx 2018.01.18
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-01-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读