Create 56.合并区间(中等).md

JavaCodeMing · JavaCodeMing · commit 85bc86e0fa6c · 2020-08-24T20:11:24.000+08:00
diff --git a/Algorithm/56.合并区间(中等).md b/Algorithm/56.合并区间(中等).md
@@ -0,0 +1,44 @@
+```text
+��Ŀ: ����һ������ļ���,��ϲ������ص�������;
+    ʾ�� 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.˫ָ��:
+    [1]˼·:
+        (1)����δָ�������ź���,�����������º���������ϲ�,������ȶԶ�ά��������;
+            (��ÿ���ڲ�����ĵ�һ��Ԫ�ش�С��������)
+        (2)��������ָ��,һ��������������(�ڲ��������ڵ��±�),һ������������������ڲ�����λ��(���ӻ�ϲ�);
+        (3)�����״����ӻ������������ĵ�һ��Ԫ��С�������ӵ����һ������ĵڶ���Ԫ��,��ֱ�����ӵ��������;
+        (4)������Ҫ��������ĺϲ�,���һ��Ԫ�����ź����,ȡ����������ڶ���Ԫ�ص����ֵ��Ϊ�ϲ�������ĵڶ���Ԫ��;
+    [2]ʵ��:
+		class Solution {
+			public int[][] merge(int[][] intervals) {
+				int len = intervals.length;
+				if (len <= 1) {
+					return intervals;
+				}
+				// ���ڲ�����ĵ�һ��Ԫ�صĴ�С������
+				Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
+				int[][] result = new int[len][2];
+				int index = -1;
+				// for(int i=0;i<intervals.length;i++){}�򻯶���
+				for (int[] interval : intervals) {
+					if (index == -1 || result[index][1] < interval[0]) {
+						result[++index] = interval;
+					} else {
+						result[index][1] = Math.max(result[index][1], interval[1]);
+					}
+				}
+				return Arrays.copyOf(result, index + 1);
+			}
+		}
+	[3]���Ӷȷ���:
+        (1)ʱ�临�Ӷ�:O(n)
+	        ����nΪintervals����ĳ���,ֻ��Ҫ����һ�����鼴����ô�;
+        (2)�ռ临�Ӷ�: O(n)
+```

-Original file line number
+Diff line change
@@ @@ -0,0 +1,44 @@ @@
 +```text
 +题目: 给出一个区间的集合,请合并所有重叠的区间;
 +    示例 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.双指针:
 +    [1]思路:
 +        (1)题中未指明数组排好序,在乱序的情况下很难做区间合并,因此首先对二维数组排序;
 +            (按每个内部数组的第一个元素从小到大排序)
 +        (2)定义两个指针,一个用来遍历数组(内部数组所在的下标),一个用来结果数组中正在操作的位置(添加或合并);
 +        (3)若是首次添加或遍历到的数组的第一个元素小于已添加的最后一个数组的第二个元素,则直接添加到结果数组;
 +        (4)否则需要进行数组的合并,因第一个元素是排好序的,取这两个数组第二个元素的最大值作为合并后数组的第二个元素;
 +    [2]实现:
 +		class Solution {
 +			public int[][] merge(int[][] intervals) {
 +				int len = intervals.length;
 +				if (len <= 1) {
 +					return intervals;
 +				}
 +				// 按内部数组的第一个元素的大小来排序
 +				Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
 +				int[][] result = new int[len][2];
 +				int index = -1;
 +				// for(int i=0;i<intervals.length;i++){}简化而来
 +				for (int[] interval : intervals) {
 +					if (index == -1 || result[index][1] < interval[0]) {
 +						result[++index] = interval;
 +					} else {
 +						result[index][1] = Math.max(result[index][1], interval[1]);
 +					}
 +				}
 +				return Arrays.copyOf(result, index + 1);
 +			}
 +		}
 +	[3]复杂度分析:
 +        (1)时间复杂度:O(n)
 +	        其中n为intervals数组的长度,只需要遍历一遍数组即可求得答案;
 +        (2)空间复杂度: O(n)
 +```