大家辛苦刷题、背项目案例，结果可能斗不过开外挂的选手。
算法题：将数据流变为多个不相交区间
插入 1：结果是 [[1, 1]] 插入 3：结果是 [[1, 1], [3, 3]] 插入 2：结果是 [[1, 3]]
解题思路
TreeSet）来存储这些区间。因为区间是有序的，我们可以借助二分查找快速定位需要处理的区间。每次插入新数字时，要做以下几步：找到新数字左边和右边的最近区间； 判断新数字是否与左、右区间相连：
如果可以与左区间相连，就扩展左区间； 如果可以与右区间相连，就扩展右区间； 如果左右都能连，就干脆把两边合并成一个区间； 如果都连不上，自己单独成一个区间。
import java.util.*;
class SummaryRanges {
private TreeSet<int[]> intervals;
public SummaryRanges() {
intervals = new TreeSet<>((a, b) -> Integer.compare(a[0], b[0]));
}
public void addNum(int value) {
// 找到右边第一个区间
int[] higher = intervals.ceiling(new int[]{value + 1, value + 1});
// 找到左边第一个区间
int[] lower = intervals.floor(new int[]{value, value});
if (lower != null && lower[1] + 1 >= value) {
// 和左区间相连
lower[1] = Math.max(lower[1], value);
if (higher != null && lower[1] + 1 >= higher[0]) {
// 左右区间合并
lower[1] = higher[1];
intervals.remove(higher);
}
} else if (higher != null && higher[0] - 1 == value) {
// 和右区间相连
higher[0] = value;
} else {
// 新区间
intervals.add(new int[]{value, value});
}
}
public List<int[]> getIntervals() {
return new ArrayList<>(intervals);
}
}
代码解析
TreeSet 的 ceiling 和 floor 方法，用它们快速找到可能与新数字相邻的区间。至于为什么选 TreeSet 呢？因为它不仅有序，还支持高效的增删查操作，插入一个数字的时间复杂度是 (O(\log n))。对于数据流这种动态输入，效率特别重要。使用示例
public static void main(String[] args) {
SummaryRanges sr = new SummaryRanges();
sr.addNum(1);
System.out.println(sr.getIntervals()); // [[1, 1]]
sr.addNum(3);
System.out.println(sr.getIntervals()); // [[1, 1], [3, 3]]
sr.addNum(2);
System.out.println(sr.getIntervals()); // [[1, 3]]
}
好了，这道题的分享就到这儿，你觉得还能优化吗？欢迎来聊聊
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
