leetcode352. Data Stream as Disjoint Intervals
leetcode352. Data Stream as Disjoint Intervals
眯眯眼的猫头鹰
发布于 2019-10-14 17:38:41
发布于 2019-10-14 17:38:41
题目要求
Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.
For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:
[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]
**Follow up:**
What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?这里面提到了一个disjoint interval的概念，它是指不相交的区间。如果新来的数据与当前的区间集产生了重合，则需要将当前的区间集进行合并。从而确保每次得到的数据集都是不相交的。
思路和代码
这道题目整体来说有两种思路，一种就是每次插入数据的时候将出现交集的区间进行合并，另一种就是在插入数据时只更新区间的范围，并不将区间合并。
这两种方案在不同特点的数据集下各有优势。第一种方法适用于数据量大区间集少的场景。因为区间集少，而每次合并带来的区间集的数据移动成本较低。后者则刚好相反，适用于区间集较多的场景，只有在读取区间集的时候，去触发合并操作。
这里是采用方案一来实现的。如果我们维护了一组有序的区间集，这时数据流中传来一个新的数字，则该数字和区间流中的区间一共有如下几种情况：
- 正好命中某个区间，则不做任何处理
- 小于区间最左值减1，则新增左侧区间
- 等于区间最左值减1，则修改区间最左值为val
- 大于区间最有值加1， 则新增右侧区间
- 等于区间最右值加1，则修改区间最右值为val
- 等于某个区间的右值加1且等于某个区间的左值减1，则合并两个区间
- 大于某个区间的右值加一且等于某个区间的左值减一，则在两个区间中新增一个区间
- 等于某个区间的右值加1，则修改区间右值为val
- 等于某个区间的左值减1，则修改区间左值为val
代码如下：
List<Pair> pairs = new ArrayList<>();
public void addNum(int val) {
if (pairs.size() == 0) {
pairs.add(new Pair(val, val));
return;
}
int left = 0, right = pairs.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (pairs.get(mid).left < val) {
left = mid + 1;
}else if (pairs.get(mid).left > val) {
right = mid - 1;
}else {
return;
}
}
if (left == 0) {
if (pairs.get(left).left == val + 1) {
pairs.get(left).left = val;
}else {
pairs.add(0, new Pair(val, val));
}
} else if (left == pairs.size()) {
if (pairs.get(left-1).right == val - 1) {
pairs.get(left-1).right = val;
}else if (pairs.get(left-1).right < val - 1) {
pairs.add(new Pair(val, val));
}
}else if (pairs.get(left-1).right == val - 1 && pairs.get(left).left == val + 1) {
pairs.get(left-1).right = pairs.get(left).right;
pairs.remove(left);
}else if (pairs.get(left-1).right == val - 1) {
pairs.get(left - 1).right = val;
}else if (pairs.get(left).left == val + 1) {
pairs.get(left).left = val;
}else if (pairs.get(left-1).right < val){
pairs.add(left, new Pair(val, val));
}
}
public int[][] getIntervals() {
int[][] result = new int[pairs.size()][2];
for (int i = 0 ; i < pairs.size() ; i++) {
result[i][0] = pairs.get(i).left;
result[i][1] = pairs.get(i).right;
}
return result;
}
public static class Pair{
int left;
int right;
public Pair(int left, int right) {
this.left = left;
this.right = right;
}
}上面的代码新建了类Pair作为区间的对象。然后使用List对区间Pair按照从小到大存储。每次调用addNum传入val时，都会利用二分法找到左边界比val大的最近的区间。找到该区间后再按照上文的判断方式逐个处理。假设数据流大小为n，区间的平均大小为m，则这种方法的时间复杂度为O(lgM*n)。但是因为判断逻辑较多，因此代码显得凌乱，可读性很差。
这里可以使用TreeMap进行优化，TreeMap默认上是最小堆的实现，它帮我们省去了大量二分法的逻辑，同时在插入区间的时候，时间复杂度也降低到O(NlgN)。只需要对边界场景进行判断即可。代码如下：
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
public void addNum(int val) {
if (treeMap.containsKey(val)) {
return;
}
Integer lowerKey = treeMap.lowerKey(val);
Integer higherKey = treeMap.higherKey(val);
if (lowerKey != null && higherKey != null && treeMap.get(lowerKey) == val - 1 && higherKey == val + 1) {
treeMap.put(lowerKey, treeMap.get(higherKey));
treeMap.remove(higherKey);
}else if (lowerKey != null && treeMap.get(lowerKey) >= val - 1) {
treeMap.put(lowerKey, Math.max(val, treeMap.get(lowerKey)));
}else if (higherKey != null && higherKey == val + 1) {
treeMap.put(val, treeMap.get(higherKey));
treeMap.remove(higherKey);
}else {
treeMap.put(val, val);
}
}
public int[][] getIntervals() {
int[][] result = new int[treeMap.size()][2];
int index = 0;
for (int key : treeMap.keySet()){
result[index][0] = key;
result[index][1] = treeMap.get(key);
}
return result;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录