题目描述
给出一个非负整数的数据流 a1,a2,…an,…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]
算法1
(平衡树)addNum(val): $O(log(n))$ getIntervals $O(n)$
addNum:
由于区间是从小到大的,所以想到要用平衡树结构,java中就是TreeMap。
利用java里的TreeMap存储区间,具体用两个这样的结构,left,right。left为区间左端点到右端点的映射,right为区间右端点到左端点的映射。首先判断val是否属于某个区间,具体做法是利用left(TreeMap结构)的floorEntry()找到小于或等于val的最大的区间左端点,若存在,判断该区间的右端点与val的关系,如果val小于或等于该区间的右端点,则不更新区间,否则,val不属于任何一个区间。这种情况下,要考虑val-1,val+1与已有区间的关系,看能否进行区间合并。具体可以分为四种情况:
1.val-1,val+1的区间都存在,那么将val-1,val+1对应的区间合并为一个。
2.val-1对应的区间不存在,val+1对应的区间存在,那么将val与val+1对应的区间合并。
3.val+1对应的区间不存在,val-1对应的区间存在,那么将val与val-1对应的区间合并。
4.val+1与val-1都不存在,则val单独为一个区间。
getIntervals:
用数组存一下left遍历的结果即可
java 代码
class SummaryRanges {
TreeMap<Integer,Integer> left,right ;
/** Initialize your data structure here. */
public SummaryRanges() {
left = new TreeMap<>() ;
right = new TreeMap<>() ;
}
public void addNum(int val) {
Map.Entry<Integer,Integer> me = left.floorEntry(val) ;
if(me != null && val<=me.getValue()){//val属于某个区间
return ;
}
Integer s = right.get(val-1) ;
Integer t = left.get(val+1) ;
if(s != null && t != null){//分四种情况讨论
left.remove(val+1) ;
right.remove(val-1) ;
left.put(s,t) ;
right.put(t,s) ;
}else if(s != null){
right.remove(val-1) ;
left.put(s,val) ;
right.put(val,s) ;
}else if(t != null){
left.remove(val+1) ;
left.put(val,t) ;
right.put(t,val) ;
}else{
left.put(val,val) ;
right.put(val,val) ;
}
}
public int[][] getIntervals() {
int[][] res = new int[left.size()][2] ;
int idx = 0 ;
for(Map.Entry<Integer,Integer> num : left.entrySet()){
res[idx][0] = num.getKey() ;
res[idx++][1] = num.getValue() ;
}
return res ;
}
}
/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();
* obj.addNum(val);
* int[][] param_2 = obj.getIntervals();
*/
优秀
大佬,为什么用HashMap不可以呀?从这个代码上看,只用到了Treemap的put,remove,get, 这些HashMap上都有呀,而且还更高效
喔喔,我知道了,是因为要输出从小到大的区间,所以利用了TreeMap的自动排序
很棒!