作为一个 data structure design 题，首先要问好到底哪个 API call 比较频繁，设计上倾向于优化哪个操作。
先写了个略粗糙的版本，维护当前所有 interval 的 list，每次插入操作的时候靠 binary search 找每个 val 的位置，然后分情况考虑。
addNum(int val) 时间复杂度 O(log n) + O(n)
getInterval() 时间复杂度 O(1)
空间复杂度 O(n)
n = 当前有效数字个数
在测试数据集上，这个方法和 TreeMap 的做法用时不相上下。
public class SummaryRanges {
List<Interval> list;
/** Initialize your data structure here. */
public SummaryRanges() {
list = new ArrayList<Interval>();
}
public void addNum(int val) {
if(list.size() == 0){
list.add(new Interval(val, val));
} else {
if(list.size() == 1){
if(val <= list.get(0).end && val >= list.get(0).start){
return;
}
}
if(val < list.get(0).start){
if(val == list.get(0).start - 1){
list.get(0).start = val;
} else {
list.add(0, new Interval(val, val));
}
return ;
} else if (val > list.get(list.size() - 1).end){
if(val == list.get(list.size() - 1).end + 1){
list.get(list.size() - 1).end = val;
} else {
list.add(new Interval(val, val));
}
return ;
}
int pos = binarySearch(list, val);
int prevEnd = list.get(pos).end;
int nextStart = list.get(pos + 1).start;
if(val <= prevEnd || val >= nextStart){
return;
} else if(val == prevEnd + 1 && val == nextStart - 1){
list.get(pos).end = list.get(pos + 1).end;
list.remove(pos + 1);
} else if(prevEnd + 1 >= val){
list.get(pos).end = Math.max(list.get(pos).end, val);
} else if(val == nextStart - 1){
int newStart = list.get(pos + 1).start - 1;
int newEnd = list.get(pos + 1).end;
// Will have MLE if don't remove
list.remove(pos + 1);
list.add(pos + 1, new Interval(newStart, newEnd));
} else {
list.add(pos + 1, new Interval(val, val));
}
}
}
public List<Interval> getIntervals() {
return list;
}
private int binarySearch(List<Interval> list, int val){
int left = 0;
int right = list.size() - 1;
while(left + 1 < right){
int mid = left + (right - left) / 2;
if(list.get(mid).start == val){
return mid;
} else if(list.get(mid).start < val){
left = mid;
} else {
right = mid;
}
}
return left;
}
}
第二个版本，自己写了个 LinkedList 维护目前所有数字，每次 call getIntervals() 的时候根据 list 当场生成。
addNum(int val) 时间复杂度 O(n);
getIntervals() 时间复杂度 O(n);
空间：O(n);
n = 当前的有效数字个数。
public class SummaryRanges {
private class Node{
Integer val;
Node next;
public Node(Integer val){
this.val = val;
this.next = null;
}
}
Node head;
/** Initialize your data structure here. */
public SummaryRanges() {
Node dummy = new Node(null);
head = dummy;
}
public void addNum(int val) {
Node cur = head.next;
Node prev = head;
while(cur != null){
if(cur.val == val) return;
if(cur.val > val){
prev.next = new Node(val);
prev.next.next = cur;
return;
}
prev = cur;
cur = cur.next;
}
prev.next = new Node(val);
}
public List<Interval> getIntervals() {
List<Interval> list = new ArrayList<Interval>();
Node cur = head.next;
Integer curStart = null;
Integer curEnd = null;
while(cur != null){
int val = cur.val;
if(curStart == null && curEnd == null){
curStart = val;
curEnd = val;
} else {
if(val == curEnd + 1){
curEnd = val;
} else {
list.add(new Interval(curStart, curEnd));
curStart = val;
curEnd = val;
}
}
cur = cur.next;
}
list.add(new Interval(curStart, curEnd));
return list;
}
}
参考了论坛代码之后，另一种巧妙的做法：
addNum(int val) 时间复杂度：O(log n)
getIntervals() 时间复杂度：o(n log n)
空间复杂度： O(n)
public class SummaryRanges {
TreeMap<Integer, Interval> tree;
public SummaryRanges() {
tree = new TreeMap<>();
}
public void addNum(int val) {
if(tree.containsKey(val)) return;
Integer l = tree.lowerKey(val);
Integer h = tree.higherKey(val);
if(l != null && h != null && tree.get(l).end + 1 == val && h == val + 1) {
// Joining two intervals
tree.get(l).end = tree.get(h).end;
tree.remove(h);
} else if(l != null && tree.get(l).end + 1 >= val) {
// Completely contained in left interval
// Try to expand end
tree.get(l).end = Math.max(tree.get(l).end, val);
} else if(h != null && h == val + 1) {
// Right next to right interval
// Merge
tree.put(val, new Interval(val, tree.get(h).end));
tree.remove(h);
} else {
// Disjoint new interval
tree.put(val, new Interval(val, val));
}
}
public List<Interval> getIntervals() {
return new ArrayList<>(tree.values());
}
}
