网站+做+app,用html做网站顺序,注册城乡规划师是干什么的,移动互联网开发技术是什么废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【合并区间】#xff0c;使用【数组】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为…废话不多说喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【合并区间】使用【数组】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。
明确目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
合并区间【MID】
一道一直想要解决的高频题用到了排序
题干 解题思路
如果我们按照区间的左端点排序那么在排完序的列表中可以合并的区间一定是连续的。如下图所示标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间它们在排完序的列表中是连续的 我们用数组 merged 存储最终的答案。
首先我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 merged 数组中并按顺序依次考虑之后的每个区间如果当前区间的左端点在数组 merged 中最后一个区间的右端点之后那么它们不会重合我们可以直接将这个区间加入数组 merged 的末尾否则它们重合我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点将其置为二者的较大值。
总体思路是左端点从小到大排列每次比较只要比较新区间的左端点是否在已合并区间右端点之后就可以了在之后则独立在之前则重叠而且由于左端点升序在之前也是在之前已合并区间的中间极端情况是和已排序区间左端点重叠
代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构无 算法快速排序分治算法、二分查找 技巧双指针 import java.util.*;/** public class Interval {* int start;* int end;* public Interval(int start, int end) {* this.start start;* this.end end;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param intervals Interval类ArrayList* return Interval类ArrayList*/public ArrayListInterval merge (ArrayListInterval intervals) {// 1 先对集合进行排序intervals.sort(Comparator.comparingInt(interval - interval.start));// 2 遍历顺序数组进行合并ArrayListInterval result new ArrayListInterval();for (Interval interval : intervals) {// 2-1 获取当前区间左右端点和已合并区间右端点int leftPoint interval.start;int rightPoint interval.end;// 2-2 如果结果区间为空或者当前区间左端点大于已合并区间右端点则当前区间作为独立子区间加入集合if (result.size() 0 || leftPoint result.get(result.size() - 1).end) {result.add(interval);} else {// 2-3 否则认为当前区间与已合并区间有重叠只需更新合并区间右端点result.get(result.size() - 1).end Math.max(result.get(result.size() - 1).end, rightPoint);}}return result;}
}leetcode数组入参的处理方法
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param n int整型 the n* return int整型*/public int[][] merge(int[][] intervals) {// 1 先对数组进行排序Arrays.sort(intervals, Comparator.comparingInt(interval-interval[0]));// 2 遍历已排序数组进行区间合并int[][] result new int[intervals.length][2];int idx -1;for (int[] interval : intervals) {// 2-1 获取当前区间左右边界以及合并区间右边界int leftPoint interval[0];int rightPoint interval[1];// 2-2 如果已合并区间为空或当前区间左端点大于已合并区间右端点则不重叠if (idx -1 || result[idx][1] leftPoint) {idx;result[idx] interval;} else {// 2-3 反之则重叠已两个区间较大值为新的右边界result[idx][1] Math.max(result[idx][1], rightPoint);}}return Arrays.copyOf(result, idx 1);}}复杂度分析
合并区间是一个常见的算法问题通常用于合并具有重叠部分的区间以简化问题或提供更清晰的表示。以下是关于合并区间问题的时间复杂度和空间复杂度的讨论
时间复杂度 时间复杂度是衡量算法性能的关键指标它表示算法在输入规模增加时所需的运行时间。对于合并区间问题一种常见的解决方法是首先将区间按照起始值进行排序然后遍历这些区间并合并它们。 排序对区间按照起始值进行排序通常需要 O(n*log(n)) 的时间复杂度其中 n 是区间的数量。 遍历和合并一旦区间排序完成遍历区间并合并重叠的部分通常需要线性时间即 O(n)。
因此综合来看合并区间的时间复杂度通常是 O(n*log(n))其中 n 是区间的数量。这是由排序操作的时间复杂度主导的。
空间复杂度 空间复杂度表示算法在执行过程中所需的额外内存空间。对于合并区间问题空间复杂度通常取决于存储合并后的区间的数据结构。 如果您在原始区间上就地修改而不创建额外的数据结构则空间复杂度是 O(1)因为不需要额外的内存空间。 如果您创建一个新的数据结构来存储合并后的区间空间复杂度将取决于这个数据结构的大小。通常情况下合并后的区间数目会少于或等于初始区间数目因此空间复杂度也是 O(n)。
总结合并区间问题的时间复杂度通常是 O(n*log(n))空间复杂度可以是 O(1) 或 O(n)具体取决于是否创建了新的数据结构来存储合并后的区间。
拓展知识Arrays的用法
Arrays的一些用法拓展描述下
Arrays.copyOf(result, x)描述了什么
Arrays.copyOf(result, x) 是一个Java方法它的含义是创建一个新数组这个新数组的长度为 x并且将原始数组 result 中的元素复制到新数组中。如果 x 小于原始数组的长度那么新数组将截断只包含原始数组中前 x 个元素。如果 x 大于原始数组的长度新数组将在末尾用默认值填充这个默认值取决于元素的数据类型例如数值类型默认是0引用类型默认是null。
这个方法允许你在不改变原始数组的情况下创建一个具有不同长度的新数组非常方便特别是在需要调整数组大小时。例如
int[] result {1, 2, 3, 4, 5};
int x 8; // 新数组的长度int[] newArray Arrays.copyOf(result, x);// 新数组现在将会是 {1, 2, 3, 4, 5, 0, 0, 0}长度为 8在这个示例中Arrays.copyOf 创建了一个长度为8的新数组并将原始数组 result 中的元素复制到新数组中多出的部分用0填充。
Arrays.sort(intervals, Comparator.comparingInt(interval-interval[0])) 描述下这个语句做了什么
这个语句使用了 Java 中的 Arrays.sort 方法来对一个二维数组 intervals 进行排序。排序是基于二维数组中每个子数组的第一个元素interval[0]的值来进行的也就是按照子数组的起始值进行排序。
具体来说这行代码的功能是 intervals 是一个二维整数数组通常用于表示区间例如区间的起始和结束值。 Arrays.sort 是 Java 中用于对数组进行排序的方法。 Comparator.comparingInt(interval - interval[0]) 是一个比较器它告诉排序方法要按照每个子数组的第一个元素interval[0]的值进行升序排序。
所以这个语句将根据 intervals 中每个子数组的第一个元素起始值来对二维数组进行排序从小到大排列。排序后intervals 数组中的子数组将按照它们的起始值从小到大的顺序排列。
这对于处理区间的问题非常有用因为它可以将区间按照起始值进行排序使得你可以更轻松地执行各种区间操作比如合并重叠区间或查找包含某个点的区间等操作。
