伍菲网站建设,东源县住房和城乡建设部网站,建设网站的目的是什么,做网站建设推荐合并区间-力扣算法题56题
以数组 intervals 表示若干个区间的集合#xff0c;其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间#xff0c;并返回 一个不重叠的区间数组#xff0c;该数组需恰好覆盖输入中的所有区间 。 示例 1#xff1a;
输入其中单个区间为 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 intervals.length 104intervals[i].length 20 starti endi 104
java实现算法代码
class Solution {public int[][] merge(int[][] intervals) {if (intervals.length 0) {return new int[0][2];}Arrays.sort(intervals, new Comparatorint[]() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});Listint[] merged new ArrayListint[]();for (int i 0; i intervals.length; i) {int L intervals[i][0], R intervals[i][1];if (merged.size() 0 || merged.get(merged.size() - 1)[1] L) {merged.add(new int[]{L, R});} else {merged.get(merged.size() - 1)[1] Math.max(merged.get(merged.size() - 1)[1], R);}}return merged.toArray(new int[merged.size()][]);}
}算法思路力扣的思路
如果我们按照区间的左端点排序那么在排完序的列表中可以合并的区间一定是连续的。如下图所示标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间它们在排完序的列表中是连续的 算法
我们用数组 merged 存储最终的答案。
首先我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中并按顺序依次考虑之后的每个区间
如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后那么它们不会重合我们可以直接将这个区间加入数组 merged 的末尾
否则它们重合我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点将其置为二者的较大值。
正确性证明
上述算法的正确性可以用反证法来证明在排完序后的数组中两个本应合并的区间没能被合并那么说明存在这样的三元组 (i,j,k) 以及数组中的三个区间 a[i],a[j],a[k] 满足 ijk 并且 (a[i],a[k])可以合并但 (a[i],a[j]) 和 (a[j],a[k]) 不能合并。这说明它们满足下面的不等式 a[i].enda[j].start(a[i] 和 a[j] 不能合并)a[j].enda[k].start(a[j] 和 a[k] 不能合并)a[i].end≥a[k].start(a[i] 和 a[k] 可以合并) a[i].enda[j].start(a[i] 和 a[j] 不能合并) a[j].enda[k].start(a[j] 和 a[k] 不能合并) a[i].end≥a[k].start(a[i] 和 a[k] 可以合并) 我们联立这些不等式可以得到 a[i].enda[j].start≤a[j].enda[k].start 产生了矛盾这说明假设是不成立的。因此所有能够合并的区间都必然是连续的。
我的思路
1.先判断该 intervals是否为空为空则返回一个空的二维数组int[0][2]
2.不为空的话先用Array.sort(T[] a,Comparator? super T c)来定制一个只比较数组的最左端并使用升序排序的Compare排序器
3.之后将二维数组封装在一个List集合里面进行下一步比较
4.有两种情况 4.1. 如果第一个区间的最右端的值小于下一个区间的最左端的值则在List集合中再添加一个区间 4.2. 如果第一个区间的最右端的值大于等于下一个区间最左端的值则将第一个区间最右端的值修改为下一个区间最右端的值
5.将List转换为数组并以二维数组的形式返回即可
使用方法Arrays.sort和Comprator
Arrays.sort使用文档 public static T void sort(T[] a, Comparator? super T c) 根据指定比较器引发的顺序对指定的对象数组进行排序。 数组中的所有元素都必须是指定比较相互比较的 即 c.compare(e1, e2)不得抛出ClassCastException任何元件e1和e2阵列中。 这种保证是稳定的 相同的元素不会因排序而重新排序。 实现注意事项此实现是一个稳定的自适应的迭代合并输出当输入数组部分排序时需要远远少于n lgn的比较同时在输入数组随机排序时提供传统mergesort的性能。 如果输入数组几乎排序则实现需要大约n次比较。 临时存储要求从几乎排序的输入数组的小常量到随机排序的输入数组的n / 2个对象引用不等。 该实现在其输入数组中具有升序和降序的相同优势并且可以利用同一输入数组的不同部分中的升序和降序。 它非常适合合并两个或多个排序数组只需连接数组并对结果数组进行排序。 参数类型 T - 要排序的对象的类 参数 a - 要排序的数组 c - 用于确定阵列顺序的比较器。 null值表示应使用元素 natural ordering 。 异常 ClassCastException - 如果数组包含使用指定比较器无法 相互比较的元素 IllegalArgumentException - 可选如果发现比较器违反了Comparator合同 Comprator使用文档 public interface ComparatorT 比较函数它对某些对象集合施加总排序 。 可以将比较器传递给排序方法例如Collections.sort或Arrays.sort 以便精确控制排序顺序。 比较器还可用于控制某些数据结构的顺序例如sorted sets或sorted maps 或者为没有natural ordering的对象集合提供排序。 比较器c对一组元素S施加的排序被认为与等号一致当且仅当c.compare(e1, e2)0具有与e1.equals(e2) e1和e2在S中的S相同的布尔值时。 当使用能够强加与equals不一致的排序的比较器来排序有序集或有序映射时应该谨慎行事。 假设具有显式比较器c的有序集或有序映射与从集合S提取的元素或键 S 。 如果c对S的排序与equals不一致则排序集或有序映射将表现得“奇怪”。 特别是有序集或有序映射将违反集合或映射的一般合同其定义为equals 。 例如假设有两个元素a和b 使(a.equals(b) c.compare(a, b) ! 0)为空TreeSet 比较器为c 。 第二个add操作将返回true并且树集的大小将增加因为a和b在树集的视角中不相等即使这与Set.add方法的规范相反。 注意这通常是一个好主意比较也能实现java.io.Serializable 因为它们可能被用来作为排序的序列化数据结构的方法如TreeSet TreeMap 。 为了使数据结构成功序列化比较器如果提供必须实现Serializable 。 对于数学上的倾斜即限定了施加顺序给定的比较器的关系 c上一组给定对象强加S是 {(x, y) such that c.compare(x, y) 0}. 此总订单的商是 {(x, y) such that c.compare(x, y) 0}. 它从合同紧跟compare 该商数是一个等价关系 S 并且实行排序是全序 S 。 当我们说c对S施加的排序与equals一致时 我们的意思是排序的商是由对象 equals(Object)方法定义的等价关系 {(x, y) such that x.equals(y)}. 与Comparable不同比较器可以选择允许比较空参数同时保持对等关系的要求。 声明 部分算法思路摘自力扣位置在算法思路这个目录里其余均为个人创作 作者力扣官方题解 链接https://leetcode.cn/problems/merge-intervals/ 来源力扣LeetCode
