设计做图免费网站,网页设计自学视频网站,制作相册书,常州免费网站建设数据结构–合并区间
分析
首先需要对整个二维数组的每一个区间的第一列#xff08;左端#xff09;进行升序#xff0c;然后因为合并之后的的区间个数不确定#xff0c;所以使用ArrayList#xff0c;然后创建一个临时变量为第一个区间#xff0c;然后比较其第二列…数据结构–合并区间
分析
首先需要对整个二维数组的每一个区间的第一列左端进行升序然后因为合并之后的的区间个数不确定所以使用ArrayList然后创建一个临时变量为第一个区间然后比较其第二列右端是否与下一个区间的左端相交注意这里是大于等于如果相交就比较他们右端点的大小把大的赋给临时变量如果不相交就往集合添加这个区间然后让临时变量为当前没有相交到的数组
代码实例
第一个我最开始的土方法看看就行
class Solution {public int[][] merge(int[][] intervals) {if(intervals.length 0){return intervals;}for(int j 0 ;j intervals.length - 1;j){for(int i 0;i intervals.length - 1 - j;i){int [] temp new int[2]; if(intervals[i][0] intervals[i 1][0]) {temp intervals[i];intervals[i] intervals[i 1];intervals[i 1] temp;}}}// 完成排序Listint [] list new ArrayList();int [] temp intervals[0];for(int i 1; i intervals.length;i){if(temp[1] intervals[i][0]){temp[1] Math.max(temp[1],intervals[i][1]);}else{list.add(temp);temp intervals[i];}}list.add(temp);return list.toArray(new int[list.size()][2]);}
}标准的
class Solution {public int[][] merge(int[][] intervals) {
if (intervals.length 0) return intervals;//1、对二维数组按照第一列升序排序Arrays.sort(intervals, (a, b) - a[0] - b[0]);//2、进行合并数组Listint [] list new ArrayList();int term[] intervals[0];//临时空间1 判断是否需要合并集合2 是否放入结果集for (int i 1; i intervals.length; i) {if (term[1]intervals[i][0]){term[1]Math.max(term[1],intervals[i][1]);}else {list.add(term);termintervals[i];}}list.add(term);return list.toArray(new int[list.size()][2]);}
}力扣的示例代码
class Solution {public int[][] merge(int[][] intervals) {int max Integer.MIN_VALUE;int min Integer.MAX_VALUE;for (int[] ints : intervals) {max Math.max(ints[1],max);min Math.min(ints[0],min);}// min index ints[0]// map数组存储的是 每个区间的起点 对应的最大的终点int[] map new int[max - min 1];Arrays.fill(map, -1);// 区间起始值相同则取最大右区间for (int[] ints : intervals) {int left ints[0] - min;map[left] Math.max(map[left], ints[1]);}//开始正常处理LinkedListint [] res new LinkedList();for (int i 0; i map.length; i) {if (map[i] -1) {continue;}int left i min;int right map[i];if (res.size() 0 || left res.getLast()[1]) {//当前区间的起始点大于上一个区间的终止点需要开辟一个新的区间res.add(new int[]{left,right});}else{if (res.getLast()[1] right) {//当前区间的终止点 大于 上一个区间的终止点则要更新区间的终止点res.getLast()[1] right;}}}return res.toArray(new int[][]{});}
}复杂度分析
时间复杂度
O(nlogn)其中 n 为区间的数量。除去排序的开销我们只需要一次线性扫描所以主要的时间开销是排序的 O(nlogn)。
空间复杂度
O(logn)其中 n 为区间的数量。这里计算的是存储答案之外使用的额外空间。 O(logn) 即为排序所需要的空间复杂度。
