PHP算法求解

Question

设，有数组：

$arr = [3, 1, 2, 4, 8, 7, 9, 10, 13, 15];

写一个函数，使其输出格式为:

$arr = array(
        0 => '1~4',
        1 => '7~10',
        2 => '13',
        3 => '15'
);

补充：
感谢已经回答的各位道友！
数组$arr的长度是不固定的，内容也是动态的，仅已知这个数组是一维数组，数组键值也可能是个字符串类型！

补充：再次谢谢诸位道友！ 我也琢磨了个函数，分享一下，望批评！

$arr = [3, 1, 2, 4, 7, 8, 9, 10, 13, 15, 15, 'sdfsf'];

function foo($arr)
{
    asort($arr);
    $cur = 0;
    $list = [];
    foreach ($arr as $k => $v){
        //如果不是数值或者是空则剔除此元素，进入下个循环
        if(!is_numeric($v) || empty($v)) {
            unset($arr[$k]);
            continue;
        }
        //如果连续中的末尾数值和当前数值相差为1，则继续压入该连续段$list[$cur]，否则建立下个连续段
        if(!empty($list[$cur]) && ($v - end($list[$cur]) > 1)){
            $cur++;
        }
        //如果连续段中已经存在该值则进入下一循环
        elseif(!empty($list[$cur]) && in_array($v, $list[$cur])){
            continue;
        }
        //压入
        $list[$cur][] = $v;
    }
    //把压好的数组进行格式化（变成 a~b ）样式
    foreach ($list as $k => $v){
        //保险起见 再排个序
        asort($v);
        //如果数组中不止一个元素
        if(count($v) > 1){
            $list[$k] = $v[0]. '~'. end($v);
        }
        else{
            $list[$k] = $v[0];
        }
    }
    return $list;
}

echo '<pre>';
var_export(foo($arr));

打印结果：

array (
  0 => '1~4',
  1 => '7~10',
  2 => 13,
  3 => 15,
)

Answer 1

看到这个问题，自己实现了哈，不是很优化，供参考

<?php
// +----------------------------------------------------------------------
// | lmxdawn [ WE CAN DO IT JUST THINK IT ]
// +----------------------------------------------------------------------
// | Copyright (c) 2016 .
// +----------------------------------------------------------------------
// | Licensed ( http://www.apache.org/licenses/LICENSE-2.0 )
// +----------------------------------------------------------------------
// | Author: Byron Sampson <[e-mail]>
// +----------------------------------------------------------------------

/*
//设，有数组：
    $arr = [3, 1, 2, 4, 8, 7, 9, 10, 13, 15];
//写一个函数，使其输出格式为:
    $arr = array(
        0 => '1~4',
        1 => '7~10',
        2 => '13',
        3 => '15'
    );
 //*/

class Test {

    private $test_array;//需要操作的数组

    private $ico = '~';//分隔符

    private static $_instance;//

    private function __construct($test_array = array()) {
        $this->test_array = $test_array;
    }

    private function __clone() {
        // TODO: Implement __clone() method.
    }

    public static function getInstance($test_array = array()){
        if (is_null(self::$_instance) || !isset(self::$_instance)){
            self::$_instance = new self($test_array);
        }
        return self::$_instance;
    }

    /**
     * 数组分组
     * @return array 返回分好的数组
     */
    public function array_group(){

        //首先 升序对数组排序
        sort($this->test_array);
        // 去重数组
        $test_array = array_unique($this->test_array);
        //定义临时数组
        $tmp_array = array();
        $one = $test_array[0];//记录第一次的值
        $tmp_array_key = -1;//临时数组的下标 （初始值为 -1）不然临时数组的下标会从 1 开始
        foreach ($test_array as $key => $val){
            // 取出临时数组的最后一个元素
            $last_val = end($tmp_array);
            // 用分隔符把字符串转换为数组
            $last_array = explode($this->ico,$last_val);
            //如果最后一个元素为数组 就去最后一个元素的最后一个元素，否则就是取第一个
            $tmp_last_val = (is_array($last_array)) ? end($last_array) : $last_array[0];
            //判断是否是连续值
            if (!empty($tmp_last_val) && ($tmp_last_val + 1) == $val){
                $val = $one.$this->ico.$val;
            }else{
                // 如果不连续，更改第一次记录的值
                $one = $val;
                // 临时数组的值加一
                $tmp_array_key++;
            }
            //存入临数组
            $tmp_array[$tmp_array_key] = $val;
        }

        return $tmp_array;//返回临时数组

    }


    /**
     * 格式化输出数组
     * @param      $var
     * @param bool $echo
     * @param null $label
     * @param bool $strict
     * @return mixed|null|string
     */
    public static function dump($var, $echo=true, $label=null, $strict=true) {
        header("Content-type: text/html; charset=utf-8");
        $label = ($label === null) ? '' : rtrim($label) . ' ';
        if (!$strict) {
            if (ini_get('html_errors')) {
                $output = print_r($var, true);
                $output = '<pre>' . $label . htmlspecialchars($output, ENT_QUOTES) . '</pre>';
            } else {
                $output = $label . print_r($var, true);
            }
        } else {
            ob_start();
            var_dump($var);
            $output = ob_get_clean();
            if (!extension_loaded('xdebug')) {
                $output = preg_replace('/\]\=\>\n(\s+)/m', '] => ', $output);
                $output = '<pre>' . $label . htmlspecialchars($output, ENT_QUOTES) . '</pre>';
            }
        }
        if ($echo) {
            echo($output);
            return null;
        }else
            return $output;
    }

}

$test_array = array(3, 1, 2, 4, 8, 7, 9, 10, 13, 15,3,1,2,4,23,56,85,24);
$test = Test::getInstance($test_array);

// 打印数组
Test::dump($test->array_group());

结果 ：

array(7) {
  [0] => string(3) "1~4"
  [1] => string(4) "7~10"
  [2] => int(13)
  [3] => int(15)
  [4] => string(5) "23~24"
  [5] => int(56)
  [6] => int(85)
}

Answer 2

$arr = [3, 1, 2, 4, 8, 7, 9, 10, 13, 15];

function array_section($arr=[], $section=[])
{
  $data = [];
  sort($arr);
  $count = count($section);
  $i = 0;
  while ($i < $count) {
    $j = 0;
    while ($j < $section[$i]) {
      $data[$i][$j] = array_shift($arr);
      ++$j;
    }
    ++$i;
  }
  return $data;
}

print_r(array_section($arr, [4, 4, 1, 1]));

Answer 3

连续的就放到一个下标下面就行。

Answer 4

先排个序 再分段吧

Answer 5

<?php
$arr = array(3, 1, 2, 4, 3,8, 7, 9, 10, 13, 15,15);

//排序
sort($arr);
$ret = array();

function sortRange($arr,&$ret){
    //缓存最大值，最小值
    $min = array_shift($arr);
    $max =  $min;
        foreach ($arr as $item){
            if($item == $max+1){//如果连续，就替换最大值，并继续
                $max = $max+1;
                array_shift($arr);
            }else if ($item == $max){//如果相等，就继续
                //FLAG_A
                array_shift($arr);
                //END_FLAG_A
            }else{//如果不连续，就输出当前结果，并进入下次迭代
                //FLAG_B
                if($max==$min){
                    $ret[] = "$min";
                }else{
                    $ret[] = "$min~$max";
                }

                if(!empty($arr)){
                    sortRange($arr,$ret);
                    return;
                }
                //END_FLAG_B
            }
        }
        //处理最后一次不进入铁代的情况
        if($max==$min){
            $ret[] = "$min";
        }else{
            $ret[] = "$min~$max";
        }
}
//调用方法
sortRange($arr,$ret);

//输出结果
print_r($ret);

如果你要把相同值展示出来，就把FLAG_A的代码，替换为iFLAG_B的代码

Answer 6

1. 強制類別轉換一維 array 的各元素；

2. 排序；

3. 檢測連續與否，並構造然輸出的 array。

Answer 7

之前在segmentfault看到mysql有问这个查询语句的。
这道题应该接近O(n)吧，先桶排，然后循环一遍就行了

Answer 8

$old_arr = [3, 1, 2, 4, 8, 7, 9, 10, 13, 15];

sort($old_arr);
$new_arr = [[]];
$i = 0;
foreach ($old_arr as $e) {
    if ($e - end($new_arr[$i]) > 1)
        $i++;
    $new_arr[$i][] = $e;

}

var_dump($new_arr);

Answer 9

看到的太迟了, 最近我也写了一个类似的. 是论文引用符号的生成, 三个以上连续就用 - 连字符