Day34 合并区间

作者: Shimmer_ | 来源:发表于2021-02-28 09:18 被阅读0次

    以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间

    https://leetcode-cn.com/problems/merge-intervals/

    示例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] 可被视为重叠区间。

    提示:

    1 <= intervals.length <= 104
    intervals[i].length == 2
    0 <= starti <= endi <= 104

    Java解法

    思路:

    • 依次遍历,判断其他区间与当前区间是否存在重叠,若存在进行合并跳出,再进行遍历
    • 若不存在加入输出数组中
    • 用到递归,所以空间占用并不是很高效
    package sj.shimmer.algorithm.m2;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * Created by SJ on 2021/2/27.
     */
    
    class D34 {
        public static void main(String[] args) {
            int[][] merge = merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
            int[][] merge1 = merge(new int[][]{{1, 4}, {4, 5}});
            int[][] merge2 = merge(new int[][]{{2,3},{2,2},{3,3},{1,3},{5,7},{2,2},{4,6}});
            for (int[] ints : merge2) {
                for (int anInt : ints) {
                    System.out.print(anInt);
                    System.out.print(",");
                }
                System.out.println("---");
            }
        }
        public static int[][] merge(int[][] intervals) {
            List<int[]> list = new ArrayList<>();
            for (int[] interval : intervals) {
                list.add(interval);
            }
            List<int[]> merge = merge(list, 0);
            return merge.toArray(new int[merge.size()][2]);
        }
        public static List<int[]> merge(List<int[]> lists,int index) {
            if (lists != null&&lists.size()>index) {
                int[] compare = lists.get(index);
                for (int i = index+1; i < lists.size(); i++) {
                    int[] interval = lists.get(i);
                    //无重叠情况
                    if (interval[0]>compare[1]||interval[1]<compare[0]) {
                        if (i==lists.size()-1) {
                            return merge(lists,++index);
                        }
                        continue;
                    }else {
                        compare[0]=Math.min(interval[0],compare[0]);
                        compare[1]=Math.max(interval[1],compare[1]);
                        lists.remove(interval);
                        return merge(lists,index);
                    }
                }
            }
            return lists;
        }
    }
    
    image

    官方解

    https://leetcode-cn.com/problems/merge-intervals/solution/he-bing-qu-jian-by-leetcode-solution/

    1. 排序

      • 先按左侧边界做升序排序,这样可以合并的区间一定是连续的

      • 然后按区间重叠方式计算要加入的数据

        public int[][] merge(int[][] intervals) {
            if (intervals.length == 0) {
                return new int[0][2];
            }
            Arrays.sort(intervals, new Comparator<int[]>() {
                public int compare(int[] interval1, int[] interval2) {
                    return interval1[0] - interval2[0];
                }
            });
            List<int[]> merged = new ArrayList<int[]>();
            for (int i = 0; i < intervals.length; ++i) {
                int L = intervals[i][0], R = intervals[i][1];
                if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                    merged.add(new int[]{L, R});
                } else {
                    merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
                }
            }
            return merged.toArray(new int[merged.size()][]);
        }
        
        image
      • 时间复杂度:O(n log n)

      • 空间复杂度:O(log n)

    相关文章

      网友评论

        本文标题:Day34 合并区间

        本文链接:https://www.haomeiwen.com/subject/xgawfltx.html