美文网首页
JavaScript - 区间列表交集(双指针法)

JavaScript - 区间列表交集(双指针法)

作者: ElricTang | 来源:发表于2020-07-28 15:25 被阅读0次

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


    输入: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]]
    
    区间列表交集.png

    完整代码:

    /**
     * @param {number[][]} A
     * @param {number[][]} B
     * @return {number[][]}
     */
    var intervalIntersection = function(A, B) {
        let res = [];
        let i = 0;
        let j = 0;
    
        while (i < A.length && j < B.length) {
            // 左指针取大的
            let left = Math.max(A[i][0], B[j][0]);
            // 右指针取小的
            let right = Math.min(A[i][1], B[j][1]);
    
            if (left <= right) res.push([left, right]);
            // 子区间上界较大的不移动
            A[i][1] > B[j][1] ? j++ : i++;
        }
        return res;
    };
    

    相关文章

      网友评论

          本文标题:JavaScript - 区间列表交集(双指针法)

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