Java实现 LeetCode 352 将数据流变为多个不相交区间
2023-09-14 08:58:05 时间
352. 将数据流变为多个不相交区间
给定一个非负整数的数据流输入 a1,a2,…,an,…,将到目前为止看到的数字总结为不相交的区间列表。
例如,假设数据流中的整数为 1,3,7,2,6,…,每次的总结为:
[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]
进阶:
如果有很多合并,并且与数据流的大小相比,不相交区间的数量很小,该怎么办?
提示:
特别感谢 @yunhong 提供了本问题和其测试用例。
class SummaryRanges {
private List<int[]> list = new ArrayList<>();
/** Initialize your data structure here. */
public SummaryRanges() {
}
public void addNum(int val) {
if (list.size() == 0) {
int[] arr = new int[2];
arr[0] = arr[1] = val;
list.add(arr);
return;
}
int insertPosition = findInsertPosition(val);
if (insertPosition == list.size()) {
if (val == list.get(list.size() - 1)[1] + 1) {
list.get(list.size() - 1)[1] = list.get(list.size() - 1)[1] + 1;
} else {
int[] arr = new int[2];
arr[0] = arr[1] = val;
list.add(arr);
}
} else if (insertPosition == 0) {
if (val == list.get(0)[0] - 1) {
list.get(0)[0] = list.get(0)[0] - 1;
} else {
int[] arr = new int[2];
arr[0] = arr[1] = val;
list.add(0, arr);
}
} else if (insertPosition > 0) {
if (val == list.get(insertPosition)[0] - 1 && val == list.get(insertPosition - 1)[1] + 1) {
int index = insertPosition - 1;
int[] front = list.get(index);
int[] behind = list.get(insertPosition);
list.remove(index);
list.remove(index);
int[] arr = new int[2];
arr[0] = front[0];
arr[1] = behind[1];
list.add(index, arr);
} else if (val == list.get(insertPosition)[0] - 1) {
list.get(insertPosition)[0] = list.get(insertPosition)[0] - 1;
} else if (val == list.get(insertPosition - 1)[1] + 1) {
list.get(insertPosition - 1)[1] = list.get(insertPosition - 1)[1] + 1;
} else {
int[] arr = new int[2];
arr[0] = arr[1] = val;
list.add(insertPosition, arr);
}
}
}
public int[][] getIntervals() {
int[][] result = new int[list.size()][];
for (int i = 0; i < list.size(); i++) {
result[i] = list.get(i);
}
return result;
}
private int findInsertPosition(int val) {
int left = 0;
int right = list.size();
while (left < right) {
int mid = (left + right) / 2;
if (val >= list.get(mid)[0] && val <= list.get(mid)[1]) return -1;
if (val < list.get(mid)[0]) right = mid;
else if (val > list.get(mid)[1]) left = mid + 1;
}
return left;
}
}
/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();
* obj.addNum(val);
* int[][] param_2 = obj.getIntervals();
*/
相关文章
- java 上传文件接口_Java接口实现文件上传
- java 104规约_IEC104规约,Java开发主站程序
- java 图片识别 tess4j_JAVA使用Tess4J进行ocr识别
- db4o java,db4o Java版性能测试评估
- java webservice实现_JAVA WebService的实现方式
- java 随机数算法_Java随机数算法原理与实现方法实例详解
- java h2 数据库_Java H2数据库
- 实现使用Java代码实现MySQL数据库连接(java连接mysql数据库代码)
- 解决Java程序连接MySQL数据库的方法(java链接mysql数据库)
- 解析Java中的Linux路径(java中linux路径)
- Linux和Java联手构建编程世界(linux.java)
- Java脚本实现Linux系统的登录(java登录Linux)
- Java运行在Linux系统上免费下载(linux java下载)
- Linux下运行Java:一步步踏上学习之路(linux下运行java)
- 使用Java连接MySQL数据库的具体操作方法(java连接mysql代码)
- 查找Java进程:Linux解决方案(linux查找java进程)
- Java锁表与Oracle数据库协调实现数据安全(java锁表oracle)
- Java配置Oracle实现稳定的跨平台数据库连接(java配置oracle)
- Java连接Oracle实现简单快捷的数据传输(java联结oracle)