Java实现 LeetCode 352 将数据流变为多个不相交区间
2024-10-09 01:06:49
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();
*/
最新文章
- （4）WebApi 跨域问题
- wpf 逻辑树与可视化树
- CSS常用浮出层的写法
- angularjs的四大特征
- Xamarin开发Android笔记：使用ZXing进行连续扫描
- 解决TryUpdateModel对象为空的问题
- MVC 理解小谈
- python调用系统命令popen、system
- Linux 命令 - kill: 向进程发送信号
- Android_GestureDetector
- Memcached在.net中的应用
- 传说中的WCF（1）：这东西难学吗？
- hdu4614 Vases and Flowers 线段树+二分
- Dapper.Rainbow 简单使用
- Linux IPC实践(12) --System V信号量(2)
- 第十二届湖南省赛G - Parenthesis （树状数组维护）
- 使用JavaScript验证用户输入的是否为正整数
- Scrum Meeting NO.10
- 深入理解ASP.NET MVC（6）
- Postman-常用方法集合