leetcode做题心得55(合并区间)

合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

注意：输入类型已于2019年4月15日更改。请重置默认代码定义以获取新方法签名。

提示：

intervals[i][0] <= intervals[i][1]

题解思路：

1.一开始我的思路是创建一个数组，数组大小为所有区间中最右端的值，然后遍历每个区间，将数组中被区间包含的位置标记，最后遍历一遍这个数组输出就好了。
2.但是这样做有个很大的弊端：比如说我的区间就两个[1,3],[1000,1002]，从3到1000中间是没有任何价值的，我们这样创建数组就浪费了太多的空间了。
3.于是我的思路就变成了先排序（按区间左端点进行排序），然后再依次遍历合并了，排序是因为经过排序之后的每个区间进行合并时，只需要考虑它后面紧挨着的区间，然后用迭代的方式可以容易的完成合并。现在的问题就是题目输入是一个二维数组呀，这怎么排序呢，对一个二维数组操作太麻烦了。于是我想到了利用map，map中的键值对形式刚好可以对应区间的左右端点，于是这道题目就这样完成了。

代码：

class Solution {
    public int[][] merge(int[][] intervals) {
        int n=intervals.length;
        if(n<=1){
            return intervals;
        }
        //使用一个map保存更新后的区间
        Map<Integer,Integer> resMap =new HashMap<>();
        //用一个map将每个区间左端和右端的值保存到map中
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<n;i++){
            //如果已经存在具有相同左端点的区间，那么更新这个区间
            if(map.containsKey(intervals[i][0])){
                //新的区间右端点的值
                int nRight=Math.max(intervals[i][1],map.get(intervals[i][0]));
                map.put(intervals[i][0],nRight);
            }
            else
                map.put(intervals[i][0],intervals[i][1]);
        }
        //下面对map中的所有项按照key值进行升序排列
        List<Map.Entry<Integer,Integer>> entryList =new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
        Collections.sort(entryList, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return (o1.getKey()-o2.getKey());
            }
        });
        //将map中重合的区间合并输出到新的map中
        resMap = mergeMap(entryList);
        //获取resMap的大小
        int size = resMap.size();
        //创建需要返回的二维数组
        int[][] res =new int[size][2];
        Set<Map.Entry<Integer,Integer>> entrySet =resMap.entrySet();
        int index=0;
        for(Map.Entry<Integer,Integer> entry:entrySet){
            res[index][0]=entry.getKey();
            res[index][1]=entry.getValue();
            index++;
        }

        return res;
    }

    public Map<Integer,Integer> mergeMap(List<Map.Entry<Integer,Integer>> list){
        Map<Integer,Integer> newMap = new HashMap<Integer, Integer>();
        Iterator<Map.Entry<Integer,Integer>> it = list.iterator();
        Map.Entry<Integer,Integer> first=it.next();
        int l_left=first.getKey();
        int l_right=first.getValue();
        while(it.hasNext()){
            Map.Entry<Integer,Integer> entry =it.next();
            int left=entry.getKey();
            int right=entry.getValue();
            //需要合并
            if(left<=l_right){
                //更新l_right的值
                l_right=Math.max(l_right,right);
            }
            else{
                newMap.put(l_left,l_right);
                l_left=left;
                l_right=right;
            }
        }
        //因为最后一个区间在while循环里没有添加进去，单独添加
        newMap.put(l_left,l_right);
        return newMap;
    }
}

最后编辑于：2020.10.14 20:41:57