刷
June-20-2019
以前做的有问题，感觉遇到重复的会错，但是parameter变了，不好测了= =
这个题还是值得记一下的。其实是插入多个[1,1]这种interval。无非是跟前后判断就那么几种情况：
- 左右相连，那一起MREGE，然后删掉后面的
- 只和一边连，
- 都不连
- 其中一边囊括，
更重要等是一些general java 的相关
TreeMap
- Key是排序的，可自定义comparator
- lowerKey(), higherKey() 返还上一个，下一个存在的key
- get(), remove(), containsKey(), lowerKey(), higherKey()都是O(lgN)
Stream
- toArray(int[][]::new)
addNum: O(lgN) 做了好几次lgN: containsKey, lowerKey, higherKey, get()都是lgN
getInterval: O(N) 取决于最后有多少个interval
class SummaryRanges {
TreeMap<Integer, int[]> map;
/** Initialize your data structure here. */
public SummaryRanges() {
map = new TreeMap<>();
}
public void addNum(int val) {
if (map.containsKey(val)) return;
Integer prevKey = map.lowerKey(val);
Integer nextKey = map.higherKey(val);
if (prevKey != null && map.get(prevKey)[1] + 1 == val
&& nextKey != null && map.get(nextKey)[0] - 1 == val) {
map.get(prevKey)[1] = map.get(nextKey)[1];
map.remove(nextKey);
} else if (prevKey != null && map.get(prevKey)[1] + 1 == val) {
map.get(prevKey)[1] = val;
} else if (nextKey != null && map.get(nextKey)[0] - 1 == val) {
map.put(val, new int[]{val, map.get(nextKey)[1]});
map.remove(nextKey);
} else if (prevKey != null && map.get(prevKey)[1] >= val){
return;
} else {
map.put(val, new int[]{val, val});
}
}
public int[][] getIntervals() {
return map.entrySet()
.stream()
.map(entry -> new int[]{entry.getValue()[0], entry.getValue()[1]})
.toArray(int[][]::new);
}
}
/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();
* obj.addNum(val);
* int[][] param_2 = obj.getIntervals();
*/
Follow up: What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?
lots of merges说得很隐晦，其实指的是，很多次的进行add() -> 需要addNum()快一些。
log(n)已经很快了。。不知道怎么提速
然后最后interval少, getInterval()的 O(N)里N代表多少个区间，也很小，正好。。
(FB) 脸家给的follow-up是，addInterval()，不再是[2,2]这种，可以是[2,6]
楞做的话就 treeMap按照start排序
分情况
- 完全包含在现有区间->无视
- 完全不包含->加入新区间
- 连接前后2个区间 -> merge
- 和前后其中1个包含 -> 前后merge
- 包含好几个现有区间 -> 最小start，最大end
仔细想想也挺麻烦。。