东莞易进网络专业网站建设 网站,免费手机wap建站,羽毛球赛事在哪看,网站建设哪家稳妥一、题目描述 给你一个由非负整数 a1, a2, ..., an 组成的数据流输入#xff0c;请你将到目前为止看到的数字总结为不相交的区间列表。
实现 SummaryRanges 类#xff1a;
SummaryRanges() 使用一个空数据流初始化对象。void addNum(int val) 向数据流中加入整数 val 。int…一、题目描述 给你一个由非负整数 a1, a2, ..., an 组成的数据流输入请你将到目前为止看到的数字总结为不相交的区间列表。
实现 SummaryRanges 类
SummaryRanges() 使用一个空数据流初始化对象。void addNum(int val) 向数据流中加入整数 val 。int[][] getIntervals() 以不相交区间 [starti, endi] 的列表形式返回对数据流中整数的总结。 示例
输入
[SummaryRanges, addNum, getIntervals, addNum, getIntervals, addNum, getIntervals, addNum, getIntervals, addNum, getIntervals]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
输出
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]解释
SummaryRanges summaryRanges new SummaryRanges();
summaryRanges.addNum(1); // arr [1]
summaryRanges.getIntervals(); // 返回 [[1, 1]]
summaryRanges.addNum(3); // arr [1, 3]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]]
summaryRanges.addNum(7); // arr [1, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2); // arr [1, 2, 3, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]]
summaryRanges.addNum(6); // arr [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]提示
0 val 10^4最多调用 addNum 和 getIntervals 方法 3 * 10^4 次
二、解题思路
在查找可以合并的区间时我们使用while循环来找到第一个结束位置小于val的区间并记录其索引i。接下来我们检查左边区间是否可以合并即左区间结束位置加一等于val。我们也检查右边区间是否可以合并即右区间开始位置减一等于val。如果两个条件都满足说明可以同时合并左边和右边区间我们需要合并这两个区间并从列表中移除右边的区间。如果只有一个条件满足则不需要进行额外的操作因为已经通过上面的步骤合并了区间。如果两个条件都不满足说明val是一个新的区间我们需要在索引i的位置插入新的区间。
三、具体代码
import java.util.ArrayList;
import java.util.List;public class SummaryRanges {Listint[] intervals;boolean[] added;public SummaryRanges() {intervals new ArrayList();added new boolean[10001]; // 因为题目中提示 0 val 10^4}public void addNum(int val) {if (added[val]) return; // 如果数字已经添加过直接返回added[val] true;// 查找可以合并的区间int i 0;while (i intervals.size() intervals.get(i)[1] val) {i;}// 尝试合并区间boolean leftMerged false, rightMerged false;if (i 0 intervals.get(i - 1)[1] 1 val) {intervals.get(i - 1)[1] val;leftMerged true;}if (i intervals.size() intervals.get(i)[0] - 1 val) {intervals.get(i)[0] val;rightMerged true;}if (leftMerged rightMerged) {// 合并两个区间intervals.get(i - 1)[1] intervals.get(i)[1];intervals.remove(i);} else if (!leftMerged !rightMerged) {// 如果没有合并到任何区间则新增一个区间intervals.add(i, new int[]{val, val});}}public int[][] getIntervals() {return intervals.toArray(new int[0][]);}
}四、时间复杂度和空间复杂度
1. 时间复杂度 addNum(int val) 方法的时间复杂度 added[val] 的访问是常数时间操作复杂度为 O(1)。while 循环在最坏情况下会遍历整个 intervals 列表复杂度为 O(n)其中 n 是 intervals 列表的长度。合并区间的操作包括检查和可能的合并是常数时间操作复杂度为 O(1)。intervals.remove(i) 的操作在最坏情况下是 O(n)因为可能需要移动元素。intervals.add(i, new int[]{val, val}) 的操作在最坏情况下也是 O(n)因为可能需要移动元素。综合以上addNum 方法的时间复杂度是 O(n)。 getIntervals() 方法的时间复杂度 toArray 方法的时间复杂度是 O(n)其中 n 是 intervals 列表的长度。因此getIntervals() 方法的时间复杂度也是 O(n)。
整体来看该代码的时间复杂度主要取决于 addNum 方法为 O(n)。
2. 空间复杂度
intervals 列表的空间复杂度是 O(n)其中 n 是区间列表中元素的数量。added 数组的空间复杂度是 O(1)因为其大小是固定的为 10001。
综合以上该代码的整体空间复杂度是 O(n 1)可以简化为 O(n)其中 n 是区间列表中元素的数量。
五、总结知识点 类定义 public class SummaryRanges定义了一个公共类SummaryRanges。 成员变量 Listint[] intervals定义了一个列表用于存储区间其中每个区间是一个整型数组。boolean[] added定义了一个布尔数组用于跟踪某个值是否已经被添加到区间中。 构造方法 public SummaryRanges()类的构造方法用于初始化成员变量。 方法定义 public void addNum(int val)定义了一个公共方法addNum用于添加一个新数字到区间集合中。public int[][] getIntervals()定义了一个公共方法getIntervals用于获取当前所有区间的二维数组。 条件语句 if (added[val]) return;使用了条件语句来检查是否已经添加过该值如果是则直接返回。 循环结构 while (i intervals.size() intervals.get(i)[1] val)使用while循环来查找可能合并的区间。 逻辑运算 leftMerged true 和 rightMerged true使用了布尔变量来跟踪是否发生了区间合并。 数组操作 intervals.get(i - 1)[1] val通过索引直接修改数组中的元素。intervals.remove(i)从列表中移除指定索引的元素。intervals.add(i, new int[]{val, val})向列表中的指定位置添加新元素。 列表操作 intervals.toArray(new int[0][])将列表转换为数组。 数据结构 ArrayList使用了ArrayList来存储区间列表。int[]使用了整型数组来表示区间。 内存管理 boolean[] added使用固定大小的布尔数组来跟踪添加的状态这是一种空间换时间的做法。 边界条件处理 代码中处理了多种边界条件如新数字是否可以合并到现有区间的前面或后面以及是否需要合并两个相邻区间。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
