锐客网

  1. 首页 > it技术 > >

LeetCode|【每日一题】——合并区间

java后端算法leetcode面试

??写在前面
  • 这里是温文艾尔的学习之路
  • 如果对你有帮助，给博主一个免费的点赞以示鼓励把QAQ
  • 博客主页 温文艾尔的学习小屋
  • ??更多文章?请关注温文艾尔主页
  • 文章发布日期：2022.03.03
  • java学习之路！
  • 欢迎各位点赞评论收藏??
  • 冲冲冲
  • ??上一篇内容：【备战面试】面试题打卡——Mysql相关面试题总结

文章目录
  • 合并区间
  • 方法1-暴力法
  • 方法2

合并区间 来源：力扣（LeetCode）
链接：点击跳转
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 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-暴力法
从i=1开始遍历intervals数组，当intervals[i]和intervals[i-1]处于重叠状态，就让intervals[i]的范围变为两者相比较的最小和最大，比如[1,3]和[2,6]，[2,6]变为[1,6]，同时标记intervals[i-1]为true
以此类推，遍历完intervals数组，新建LinkedList，将标记数组flag中为false对应的intervals中的元素添加到LinkedList中
public int[][] merge(int[][] intervals) { //int[][] nums = new int[intervals.length][2]; LinkedList nums = new LinkedList(); boolean[] flag = new boolean[intervals.length]; if (intervals.length==1) return intervals; Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0])); for (int i = 1; i < intervals.length; i++) { if (intervals[i][0]<=intervals[i-1][1]){ intervals[i][0] = Math.min(intervals[i][0],intervals[i-1][0]); intervals[i][1] = Math.max(intervals[i][1],intervals[i-1][1]); flag[i-1]=true; } } //将标记为false的添加进nums数组 int i=0; while (i

LeetCode|【每日一题】——合并区间
文章图片

方法2
既然要合并区间，就需要知道合并的区间的最小范围和最大范围，我们先让数组按从下到大的顺序排序，先令当前要合并区间的最小范围是intervals[0][0]，从i=1开始遍历intervals数组，当intervals[i]与intervals[i-1]重合，就让intervals[ i ][1]变为两个范围中的最大范围，比如[1,4]和[2,3]，[2,3]变为[2,4]，当intervals[i]与intervals[i-1]不重合时，我们这时候直到了之前范围的最小和最大范围，将这个范围添加到LinkedList中即可
public int[][] merge(int[][] intervals) { LinkedList nums = new LinkedList(); if (intervals.length==1) return intervals; Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0])); int start = intervals[0][0]; for (int i = 1; i < intervals.length; i++) { if (intervals[i][0]<=intervals[i-1][1]){ intervals[i][1] = Math.max(intervals[i][1],intervals[i-1][1]); }else { nums.add(new int[]{start,intervals[i-1][1]}); start=intervals[i][0]; } } nums.add(new int[]{start,intervals[intervals.length-1][1]}); return nums.toArray(new int[nums.size()][2]); }

【LeetCode|【每日一题】——合并区间】LeetCode|【每日一题】——合并区间
文章图片

    推荐阅读


    上一篇：LeetCode|【每日一题】——单调递增的数字

    下一篇：Java面试题大全|【备战面试】面试题打卡——Mysql相关面试题总结