LEETCODE 986. Interval List Intersections 解题思路分析

题目大意:

区间列表的交集

给定两个由一些闭区间组成的列表,每个区间列表都是成对不相交的,并且已经排序。

返回这两个区间列表的交集。

(形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <= b。两个闭区间的交集是一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3]。)

示例:

输入:A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
输出:[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
注意:输入和所需的输出都是区间对象组成的列表,而不是数组或列表。

提示:

  • 0 <= A.length < 1000
  • 0 <= B.length < 1000
  • 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=986

解题思路分析:

  1. 从两个数组的首元素开始循环比较,如果A的右边小于B的左边,说明两个区间不相交,将区间较小(靠左)的A的下标加一。
  2. 同理,如果B的右边小于A的左边,两个区间不相交,将区间较小(靠左)的B的下标加一。
  3. 排除上述两种情况之后,当前两个区间必有相交的部分,即A与B左边的最大值为相交部分的左边,另外A与B右边的最小值为相交部分的右边。然后将右边较小的一方下标加一。如果两个区间的右边相同,A和B的下标同时加一。
  4. 当A或者B的下标越界时,推出循环。

实现代码:

public int[][] intervalIntersection(int[][] A, int[][] B) {
    int indexA=0,indexB=0;
    List<int[]> list=new ArrayList<>();
    while(indexA<A.length&&indexB<B.length){
        int al=A[indexA][0], bl=B[indexB][0];
        int ar=A[indexA][1], br=B[indexB][1];
        if(ar<bl){ // 不相交,A在B左边
            indexA++;
            continue;
        }
        if(br<al){ // 不相交,B在A左边
            indexB++;
            continue;
        }
        int l=Math.max(al,bl); // 相交区间的左边
        int r=Math.min(ar,br); // 相交区间的右边
        list.add(new int[]{l,r});
        if(ar==br){
            indexA++;
            indexB++;
        }else if(ar<br) indexA++;
        else indexB++;
    }
    int[][] res=new int[list.size()][2];
    for(int i=0;i<list.size();i++){
        res[i]=list.get(i);
    }
    return res;
}

本题解法执行时间3ms。

Runtime: 3 ms, faster than 76.53% of Java online submissions for Interval List Intersections.

Memory Usage: 40.2 MB, less than 97.30% of Java online submissions for Interval List Intersections.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-986-interval-list-intersections-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。