当前位置： 首页 > article >正文

力扣 56.合并区间——Java

article 2024/10/23 1:33:47

题目要求：

以数组 intervals 表示若干个区间的集合，其中单个区间为 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 <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

题解：

import java.util.Arrays;
import java.util.ArrayList;

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 0) {
            return new int[0][0];
        }
        
        // 按照每个区间的起始值进行排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        ArrayList<int[]> merged = new ArrayList<>();
        int[] currentInterval = intervals[0];
        
        for(int i = 1; i < intervals.length; i++) {
            // 如果当前区间的结束值大于或等于下一个区间的起始值，则合并
            if(currentInterval[1] >= intervals[i][0]) {
                currentInterval[1] = Math.max(intervals[i][1], currentInterval[1]);// 更新结束值
            }else {
                merged.add(currentInterval);// 没有重叠，添加当前区间
                currentInterval = intervals[i]; // 更新当前区间
            }
        }
        // 添加最后一个区间
        merged.add(currentInterval);
        return merged.toArray(new int[merged.size()][]);
 	       
    }
}

本解法运用了数组和列表的相关知识

代码详解：

  1. 导入包：

    import java.util.Arrays;
import java.util.ArrayList;
    • Arrays：用于数组的排序和操作。
    • ArrayList：用于动态数组，可以根据需要添加或删除元素。

  2. 类定义：

    class Solution {
    • 定义一个名为 Solution 的类，通常在 LeetCode 等平台上使用这个类来包含解题方法。

  3. 合并区间方法：

    public int[][] merge(int[][] intervals) {
    • 定义一个公共方法 merge，接受一个二维数组 intervals，其中每个子数组表示一个区间，返回合并后的区间数组。

  4. 边界条件处理：

    if (intervals.length == 0) {
    return new int[0][0];
}
    • 如果输入的区间数组为空，直接返回一个空的二维数组。

  5. 排序：

    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    • 使用 Arrays.sort 对区间按起始值进行排序。排序后，相邻的区间更容易进行合并。

  6. 初始化合并列表：

    ArrayList<int[]> merged = new ArrayList<>();
int[] currentInterval = intervals[0];
    • 创建一个 ArrayList 用于存储合并后的区间。
    • 初始化 currentInterval 为第一个区间。

  7. 遍历区间：

    for (int i = 1; i < intervals.length; i++) {
    • 从第二个区间开始遍历（i = 1），因为第一个区间已经被初始化为 currentInterval。

  8. 合并逻辑：

    if (currentInterval[1] >= intervals[i][0]) {
    currentInterval[1] = Math.max(currentInterval[1], intervals[i][1]); // 更新结束值
} else {
    merged.add(currentInterval); // 没有重叠，添加当前区间
    currentInterval = intervals[i]; // 更新当前区间
}
    • 检查当前区间的结束值是否大于或等于下一个区间的起始值：
      • 如果是：表示有重叠，更新当前区间的结束值为两个区间结束值中的较大者。
      • 如果不是：表示没有重叠，将当前区间添加到 merged 列表，并更新 currentInterval 为当前遍历的区间。

  9. 添加最后一个区间：

    merged.add(currentInterval);
    • 在循环结束后，将最后一个处理的区间添加到 merged 列表。

  10. 返回结果：

    return merged.toArray(new int[merged.size()][]);
    • 将 ArrayList 转换为二维数组并返回。

运行流程

假设输入为 [[1,4],[2,3],[4,5]]：

  1. 输入处理：intervals 为 [[1, 4], [2, 3], [4, 5]]，长度不为零。
  2. 排序：排序后仍为 [[1, 4], [2, 3], [4, 5]]。
  3. 初始化：
    • merged = []
    • currentInterval = [1, 4]
  4. 遍历区间：
    • i = 1: intervals[1] 为 [2, 3]，currentInterval[1] (4) >= intervals[1][0] (2)，合并，currentInterval 更新为 [1, 4]。
    • i = 2: intervals[2] 为 [4, 5]，currentInterval[1] (4) >= intervals[2][0] (4)，合并，currentInterval 更新为 [1, 5]。
  5. 结束循环：将 currentInterval [1, 5] 添加到 merged。
  6. 返回结果：返回 [[1, 5]]。

相关拓展知识：

一、两个导入的包：

import java.util.Arrays; 和 import java.util.ArrayList; 是 Java 标准库中的内置类。下面是它们的详细说明：

1. java.util.Arrays

  • 功能：提供了用于操作数组的各种方法，如排序、搜索和比较等。

  • 常用方法：

    • Arrays.sort(...)：用于对数组进行排序。
    • Arrays.copyOf(...)：用于复制数组。
    • Arrays.equals(...)：用于比较两个数组是否相等。
    • Arrays.toString(...)：用于将数组转换为字符串表示。
2. java.util.ArrayList

  • 功能：ArrayList 是一个可变大小的数组实现，提供了动态数组的功能，可以根据需要自动调整大小。

  • 常用方法：

    • add(...)：向列表中添加元素。
    • remove(...)：从列表中移除指定元素。
    • get(...)：获取指定索引位置的元素。
    • size()：返回列表中元素的数量。
    • toArray(...)：将列表转换为数组。

总结

这两个类是 Java 集合框架中的一部分，提供了强大的数组和集合操作功能。你不需要额外安装或导入其他库，它们是 Java 标准库的一部分，可以直接使用。

二、列表：

列表（List）是编程中一种常用的数据结构，用于存储一组有序的元素。以下是关于列表的详细解释，包括其特点、常用操作以及在 Java 中的实现。

1. 列表的特点
  • 有序性：列表中的元素是有序的，元素的插入顺序与访问顺序相同。
  • 可重复性：列表可以包含重复的元素，即同一个值可以出现多次。
  • 动态大小：列表的大小可以动态调整，可以根据需要添加或删除元素。
2. 常见操作

列表通常支持以下基本操作：

  • 添加元素：
    • 在列表的末尾添加元素。
    • 在指定索引位置插入元素。
  • 删除元素：
    • 根据元素值删除第一个匹配的元素。
    • 根据索引删除元素。
  • 访问元素：
    • 通过索引访问列表中的元素。
  • 查找元素：
    • 查找元素在列表中的索引。
  • 遍历：
    • 使用循环或迭代器遍历列表中的所有元素。
3. Java 中的列表实现

在 Java 中，列表通常通过 List 接口及其实现类进行表示。最常用的实现类是 ArrayList 和 LinkedList。

a. ArrayList
  • 特性：基于动态数组实现，支持快速随机访问。
  • 性能：在添加元素时，特别是添加到末尾时性能较好；在中间插入和删除元素时性能较差，因为需要移动元素。
b. LinkedList
  • 特性：基于双向链表实现，适合频繁插入和删除操作。
  • 性能：在插入和删除元素时性能较好，但随机访问性能较差。
4. 示例代码

以下是一个使用 ArrayList 的简单示例：

import java.util.ArrayList;

public class ListExample {
    public static void main(String[] args) {
        // 创建一个 ArrayList
        ArrayList<String> list = new ArrayList<>();

        // 添加元素
        list.add("Apple");
        list.add("Banana");
        list.add("Orange");

        // 访问元素
        System.out.println("第一个元素: " + list.get(0)); // 输出: Apple

        // 删除元素
        list.remove("Banana");

        // 遍历列表
        for (String fruit : list) {
            System.out.println(fruit);
        }
    }
}

总结

列表是一种灵活且强大的数据结构，适用于存储和操作有序的数据。Java 提供了多种实现，可以根据具体需求选择合适的列表类型。

三、数组的线性排序：

Arrays.sort(...) 方法使用 Integer.compare(...) 返回的值来确定数组元素的顺序。具体来说，排序背后的机制是这样的：

1. 返回值的意义
  • Integer.compare(a, b)

    返回值:

    • 负数：表示 a 小于 b，在排序中 a 应该排在 b 前面。
    • 零：表示 a 等于 b，在排序中它们的位置不变。
    • 正数：表示 a 大于 b，在排序中 a 应该排在 b 后面。
2. 排序方法
  • Arrays.sort(...) 使用的是一个比较器，可以是自定义的（如你使用的 Lambda 表达式），也可以使用默认的自然顺序。
  • 该方法可以用于升序和降序排序，具体取决于比较器的实现。
3. 升序与降序排序
  • 升序排序：如果你想按升序排序，可以使用 Integer.compare(a, b)，如之前的代码所示。
  • 降序排序：如果你想按降序排序，只需修改比较器的实现，例如：
Arrays.sort(intervals, (a, b) -> Integer.compare(b[0], a[0]));

在这个例子中，比较器变成了 Integer.compare(b[0], a[0])，这会导致数组按照起始值从大到小排序。

示例代码

以下是一个完整的示例，展示如何进行升序和降序排序：

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[][] intervals = {{5, 7}, {1, 3}, {2, 6}, {8, 10}, {15, 18}};

        // 升序排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        System.out.println("升序排序结果: " + Arrays.deepToString(intervals));

        // 降序排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(b[0], a[0]));
        System.out.println("降序排序结果: " + Arrays.deepToString(intervals));
    }
}
输出结果

运行上述代码，输出将会是：

升序排序结果: [[1, 3], [2, 6], [5, 7], [8, 10], [15, 18]]
降序排序结果: [[15, 18], [8, 10], [5, 7], [2, 6], [1, 3]]

总结

  • Integer.compare(...) 返回的值用于确定元素的顺序。
  • Arrays.sort(...) 可以根据比较器的不同实现进行升序或降序排序。

四、Arrays.sort(...)使用方法：

1. 排序一维整型数组
import java.util.Arrays;

public class SortArrayExample {
    public static void main(String[] args) {
        int[] numbers = {5, 2, 8, 1, 3};
        
        // 排序数组
        Arrays.sort(numbers);
        
        // 输出排序后的数组
        System.out.println(Arrays.toString(numbers)); // [1, 2, 3, 5, 8]
    }
}
2. 排序一维字符数组
import java.util.Arrays;

public class SortCharArrayExample {
    public static void main(String[] args) {
        char[] chars = {'d', 'a', 'c', 'b'};
        
        // 排序字符数组
        Arrays.sort(chars);
        
        // 输出排序后的字符数组
        System.out.println(Arrays.toString(chars)); // [a, b, c, d]
    }
}
3. 排序一维浮点数组
import java.util.Arrays;

public class SortFloatArrayExample {
    public static void main(String[] args) {
        double[] numbers = {3.14, 2.71, 1.41, 1.73};
        
        // 排序浮点数组
        Arrays.sort(numbers);
        
        // 输出排序后的浮点数组
        System.out.println(Arrays.toString(numbers)); // [1.41, 1.73, 2.71, 3.14]
    }
}
4. 自定义排序

如果你需要根据特定的规则进行排序，可以使用 Arrays.sort() 方法的重载版本，传入一个比较器。例如，排序对象数组或按降序排序：

import java.util.Arrays;

public class CustomSortExample {
    public static void main(String[] args) {
        Integer[] numbers = {5, 2, 8, 1, 3};
        
        // 按降序排序
        Arrays.sort(numbers, (a, b) -> b - a);
        
        // 输出排序后的数组
        System.out.println(Arrays.toString(numbers)); // [8, 5, 3, 2, 1]
    }
}

总结

Arrays.sort(...) 方法非常强大且灵活，能够排序一维数组以及支持自定义排序规则。


http://www.kler.cn/news/360915.html

相关文章：

  • 让你的 IDEA 使用更流畅 | IDEA内存修改
  • 【GIT】.cr、.gitattributes 、 .gitignore和.git各文件夹讲解介绍
  • 使用milvus数据库实现文本相似比较
  • 打造高性能在线电子表格：WebGL 渲染引擎 Kola2d 自研之路
  • Linux·文件与IO
  • 【Vue】Vue（八）Vue3.0 使用ref 和 reactive创建响应式数据
  • 【linux】线程 (三)
  • Linux系统基础-进程间通信(3)_模拟实现匿名管道
  • 曝iPhone 18 Pro Max首发2nm芯片：内存升级12GB
  • leetcode 刷题day44动态规划Part13（ 647. 回文子串、516.最长回文子序列）
  • Kubescape 扫描和修复容器镜像漏洞
  • win10系统.net framework 3.5sp1组件怎么开启？
  • 自动化数据处理：使用Selenium与Excel打造的数据爬取管道
  • 【操作系统使用】Linux 命令行基础：文件、目录、磁盘操作及其他常用命令
  • Vision China 2024 | 移远通信以一体化的AI训练及部署能力，引领3C电子制造智能升级
  • usb 接口 线序
  • 第J5周：DenseNet+SE-Net实战（TensorFlow版）
  • Qt窗体ui如何设置中英文翻译？
  • 单链表的建立
  • 软考（网工）——网络操作系统与应用服务器