不用下载直接浏览的网站,做模板网站怎么放视频教程,wordpress文章导航插件,企业官方网站地址怎么填文章目录 1、问题2、示例3、解决方法#xff08;0#xff09;方法0——双指针#xff08;错误思路#xff09;#xff08;1#xff09;方法1——双指针#xff08;正确#xff09; 总结 1、问题 以数组 intervals 表示若干个区间的集合#xff0c;其中单个区间为 inte… 文章目录 1、问题2、示例3、解决方法0方法0——双指针错误思路1方法1——双指针正确 总结 1、问题 以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。 2、示例 示例 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] 可被视为重叠区间。 3、解决方法
0方法0——双指针错误思路 错误思路把二维数组变为一维数组排序后进行双指针。虽然这样用示例一是有效果的如下图 let intervals [[1,3],[2,6],[4,5],[15,18]]
var merge function(intervals) {let newArray [];intervals.forEach(item {newArray.push( ...item)});newArray.sort((a,b){ return a-b}) // 排序// newArray new Set(...newArray);// console.log(aa, newArray);let left0,right1;let arr []arr.push(newArray[0])while(right newArray.length) {if(newArray[left] 1 ! newArray[right] newArray[left] 1 ! newArray[right]) {arr.push(newArray[right])} leftright}console.log(res, arr);
};
merge(intervals);将intervals改为[[1,3],[2,6],[4,5],[15,18]]应该返回 [1,6,15,18]实际上返回为[1, 15, 18],并不能返回偶数的数据最后进行两两放到一个新数组中 1方法1——双指针正确
let intervals [[2,6],[1,3],[8,10],[15,18]]
var merge function(intervals) {// 1: 排序将二维数组的第一项进行排序// 二维数组的第一个相等就根据第二个排序不想等就根据第一个排序// 排的是二维数组的第一个不是二维数组里面每一个数组的第一个第二个排序// 如[[2,6],[1,3],[8,10],[15,18]] 变成[[1,3],[2,6],[8,10],[15,18]]intervals.sort((a,b) a[0] b[0] ? a[1] - b[1]: a[0] - b[0])// 2-1:定义左右指针let left intervals[0][0],right intervals[0][1];// 2-2: 定义返回符合条件的空数组let res []; // 3:遍历二维数组获取每一项进行比较intervals.forEach((item, index) {debugger// 4 如果遍历后的第一个值大于右指针说明在一个区间将当前这个区间的左右指针添加到数组中并将当前item的值设置为左右指针// 如[1,3] 中 1 3 不成立right 3// [2,6]中 2 3 不成立 right 6// [8,10]中 8 6 成立 将[1,6]添加到数组中并且左右指针改为当前item的值if(item[0] right) {res.push([left,right])left item[0]right item[1]} else {right item[1]}});// 5: 遍历完成后由于最后区间的值没有对比所以额外添加到数组中res.push([left, right])console.log(res, res); // 6: 返回题目效果
};
merge(intervals);总结 难度 中等 注意点使用双指针解决该问题的时候不能将二维数组扁平为一维数组进行计算。