Leetcode基础刷题之PHP解析(56. Merge Intervals)

 2019-7-29 星期一 开始吧

上一题链接Leetcode刷题之PHP解析(96. Unique Binary Search Trees)

题目描述

给定一个二维数组，合并他们的重叠的部分。

题目分析

这道题挺有意思的，如果相邻两个数组之间没有重叠的部分，那么他们还是他们，只要有重叠的部分，就需要把两组数组合并，新的数组位置0处是最小值，1处是最大值。先看我第一版的解，有bug

整体思路新建一个数组用来存储最终的结果，每次从数组中取出最后一组最为参照点，只要当前遍历数组中的第一个数大于参照点的最后一个数，说明这两个数组间没有交集，那么直接push到新数组中，否则取他们中的最小值，和最大值作为新数组的最小值和最大值。但是有一个bug就是比如下面这种情况

[[4,5][6,7],[8,9],[1,10]]

如果是这种情况，答案应该返回[1,10],按照我上面做的，结果就是[[4,5],[6,7],[1,10]],显然GG。因为给定的二维数组是无序的，我们只要把二维数组变成有序的即可。

代码实现

 /**
     * @param Integer[][] $intervals
     * @return Integer[][]
     */
    function merge($intervals) {
        if(empty($intervals)) return [];
        foreach($intervals as $key=>$val){
            $nums1[$key]=$val[0];
            $nums2[$key]=$val[1];
            
        }
        array_multisort($nums1,SORT_ASC,$nums2,SORT_ASC,$intervals);
        $res[]=$intervals[0];
        for($i=1;$i<count($intervals);$i++){
            if(end($res)[1]<$intervals[$i][0]){
                array_push($res,$intervals[$i]);
            }else{
                $res[count($res)-1][1]=max(end($res)[1],$intervals[$i][1]);
            }
        }
        return $res;
    }