把数组中的数拼接起来,求最大值(最小值)

问题分析

• 最暴力的解法就是把所有的组合都找出来, 然后排序得到最大值(或者最小值),这样还搞什么算法,直接抛弃.
• 这个问题的思路为: 在一个数组中依次选出最合适的值放在结果中. 那么问题就变成了如何选出最合适的值, 下面以求最大值为例说明:
  
  1. 对于两个数比较, 首先要考虑的就是位数的差异, 比如 9和 10 从值的大小比较, 那应该是10胜出, 但是 109 肯定没有 910大. 所以比较的时候要把位数作为判断的依据.
  2. 考虑了位数之后, 我们就来比较数字的大小:位数相同的, 数值大 的作为最合适的值 , 例如 9和8比较, 9胜出;
  3. 位数不同的, 以位数少的为基准, 从左到右逐位 比较. 位值大的胜出, 例如: 9和88比较, 9胜出; 位值相同的, 位数少的胜出,例如: 99和990比较, 99胜出.
  4. 这样下来每次选择的都是 最合适的值 ,依次组合的结果也就是我们想要的最大值.

下面是代码 php

function get_max($arr)
{
    $res = ""; // 最后的结果
    while (count($arr) > 0) {
        $max = "0";        // 存放每次选择最大值, 初始化
        $del = "";     // 存放最大值对应的数组键位, 选出最大值后从数组中删除
        foreach ($arr as $key => $value) {
            $str = (string)$value;
            $min = min($max, $value); // 选出两者较小的, 作为判断位数
            for ($i=0, $len=strlen($min); $i < $len ; $i++) { 

            // echo "len = $len  || str = $str  || max = $max || value = $value || str[$i] > max[$i] = $str[$i] > $max[$i]  <br/>";   // 这个把比较输出更直观
                // 两个逐位判断的条件
                if ( $str[$i] > $max[$i] || ($str[$i] == $max[$i] && $min == $value && $i == $len -1) ){
                    $max = (string)$value;
                    $del = $key;
                    break;
                } else if ( $str[$i] < $max[$i] ){
                    // 如果当前数字小于最大值的, 说明这个不需要再比较了
                    break;
                }
            }

        }
        // 在结果中追加本次选出的最合适的值, 两个数加个横杆更直观
        $res .= $max . "-";
        // 把选出的最大值删除
        unset($arr[$del]);
    }
    return $res;
}

测试下

$arr = [23,1,34,55,22,11,44,66,84,8,99,982,918,9];

print_r(get_max($arr));

结果是

9-99-982-918-8-84-66-55-44-34-23-22-1-11-