leetcode算法12-合并区间

标题：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals = [starti, endi] 。请你合并全部重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的全部区间 。

示例 1：

1. <strong>输入：</strong>intervals = [[1,3],[2,6],[8,10],[15,18]]
2. <strong>输出：</strong>[[1,6],[8,10],[15,18]]
3. <strong>解释：</strong>区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

复制代码

示例 2：

1. <strong>输入：</strong>intervals = [[1,4],[4,5]]
2. <strong>输出：</strong>[[1,5]]
3. <strong>解释：</strong>区间 [1,4] 和 [4,5] 可被视为重叠区间。

复制代码

代码：

1. class Solution {
2.     public int[][] merge(int[][] intervals) {
3.         //思路：数组按照左端点排序，比较后一个左端点是否小于上一个的右端点，
4.         //如果小于，可以合并。
5.         // 由于我们已经按照左端点排序，所以后一个的左端点必然大于等于合并区间的左端点，
6.         // 所以无需更新当前合并区间的左端点。
8.         //构建结果集
9.         List<int[]> ans = new ArrayList<>();
11.         //排序:仅对左端点排序
12.         Arrays.sort(intervals, (p, q) -> p[0] - q[0]);//p,q是数组
13.         //完整写法
14.         /**        Arrays.sort(intervals, new Comparator<int[]>() {
15.             public int compare(int[] interval1, int[] interval2) {
16.                 return interval1[0] - interval2[0];
17.             }
18.         });
19.         */
21.         for (int[] nums : intervals) {
22.             //比较后一个的左端点，注意从第二个开始
23.             int length = ans.size();
24.             if (length > 0 && nums[0] <= ans.get(length - 1)[1]) {
25.                 // 后一个左端点小于前一个右端点；可以合并。
26.                 //只需更新右端点的值(右端点是两个钟比较大的那个)，左端点，不管
27.                 ans.get(length - 1)[1] = Math.max(nums[1], ans.get(length - 1)[1]);
28.             } else {
29.                 //不可以合并直接加入
30.                 ans.add(nums);
31.             }
32.         }
33.         return ans.toArray(new int[ans.size()][]);
35.     }
36. }

复制代码

关键点：

1.思路：数组按照左端点排序，比力后一个左端点是否小于上一个的右端点，假如小于，可以合并（只需更新右端点的值(右端点是两个中比力大的那个)）。由于我们已经按照左端点排序，所以后一个的左端点必然大于即是合并区间的左端点，所以无需更新当前合并区间的左端点。
2.二维数组排序，Arrays.sort()重写规则，使用函数式接口，lambda表达式简写，只对数字左端排序。

排序代码详解：

1. Arrays.sort(intervals, new Comparator<int[]>() {
2.             public int compare(int[] interval1, int[] interval2) {
3.                 return interval1[0] - interval2[0];
4.             }
5.         });

复制代码

1. Arrays.sort

Arrays.sort 是 Java 中用于对数组进行排序的方法。它可以对一维数组进行自然排序（升序），也可以通过提供一个自界说的比力器来对数组进行自界说排序。
2. Comparator<int[]>

Comparator 是一个接口，用于界说对象之间的比力规则。在这个例子中，Comparator<int[]> 表示比力的是 int[] 范例的对象（即二维数组中的每个子数组）。
3. compare 方法

compare 方法是 Comparator 接口中的一个方法，用于比力两个对象。在这个例子中，它比力的是两个子数组 interval1 和 interval2。

• 参数：
  
  
  
  • interval1 和 interval2 是 int[] 范例的数组。
    
  
  
• 返回值：
  
  
  
  • 假如 interval1[0] < interval2[0]，返回负数。
    
  • 假如 interval1[0] == interval2[0]，返回 0。
    
  • 假如 interval1[0] > interval2[0]，返回正数。
    
  
  

这种返回值的设计使得 Arrays.sort 可以根据这些值来决定数组的排序顺序。
4. 排序规则

在这段代码中，排序规则是根据每个子数组的第一个元素（interval1[0] 和 interval2[0]）进行升序排序。具体来说：

• interval1[0] - interval2[0]：
  
  
  
  • 假如 interval1[0] 小于 interval2[0]，返回负数，表示 interval1 应该排在 interval2 之前。
    
  • 假如 interval1[0] 即是 interval2[0]，返回 0，表示它们的顺序可以互换。
    
  • 假如 interval1[0] 大于 interval2[0]，返回正数，表示 interval1 应该排在 interval2 之后。
    
  
  

原理

Lambda 表达式的核心是 函数式接口。函数式接口是 Java 中一种特殊的接口，它只有一个抽象方法。Comparator 就是一个典型的函数式接口，因为它只有一个抽象方法 compare。
当使用 Lambda 表达式时，Java 编译器会自动将 Lambda 表达式转换为对应的函数式接口的实现类。具体来说：

• 范例推断：
  
  
  
  • 编译器会根据上下文推断 Lambda 表达式的参数范例。在你的例子中，interval1 和 interval2 的范例被推断为 int[]，因为 Arrays.sort 的第二个参数是一个 Comparator<int[]>。
    
  
  
• 匿名类的实现：
  
  
  
  • 编译器会天生一个匿名类，实现 Comparator 接口，并将 Lambda 表达式中的逻辑转换为 compare 方法的实现。
    
  
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。