05 August 2008
将数据流变为多个不相交区间,
给你一个由非负整数 a1, a2, …, an 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。
实现 SummaryRanges 类：
1
2
3
SummaryRanges() 使用一个空数据流初始化对象。
void addNum(int val) 向数据流中加入整数 val 。
int[][] getIntervals() 以不相交区间 [starti, endi] 的列表形式返回对数据流中整数的总结。
Use TreeMap to easily find the lower and higher keys, the key is the start of the interval. Merge the lower and higher intervals when necessary. The time complexity for adding is O(logN) since lowerKey(), higherKey(), put() and remove() are all O(logN). It would be O(N) if you use an ArrayList and remove an interval from it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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) {
tree.get(l).end = tree.get(h).end;
tree.remove(h);
} else if(l != null && tree.get(l).end + 1 >= val) {
tree.get(l).end = Math.max(tree.get(l).end, val);
} else if(h != null && h == val + 1) {
tree.put(val, new Interval(val, tree.get(h).end));
tree.remove(h);
} else {
tree.put(val, new Interval(val, val));
}
}
public List<Interval> getIntervals() {
return new ArrayList<>(tree.values());
}
}
without using the TreeMap but a customized BST
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public class SummaryRanges {
class BSTNode {
Interval interval;
BSTNode left;
BSTNode right;
BSTNode(Interval in){
interval = in;
}
}
BSTNode findMin(BSTNode root) {
if (root == null) return null;
if (root.left == null ) return root;
else return findMin(root.left);
}
BSTNode remove(Interval x, BSTNode root) {
if (root == null) return null;
else if ( x == null ) return root;
else if (x.start > root.interval.end ) {
root.right = remove(x, root.right);
} else if (x.end < root.interval.start ) {
root.left = remove(x, root.left);
} else if ( root.left != null && root.right != null) {
root.interval = findMin(root.right).interval;
root.right = remove( root.interval, root.right);
} else {
root = ( root.left != null ) ? root.left : root.right;
}
return root;
}
BSTNode findKey(int val, BSTNode root) {
if (root == null) return null;
if (root.interval.start > val) {
return findKey(val, root.left);
} else if (root.interval.end < val) {
return findKey(val, root.right);
} else return root;
}
BSTNode addKey(int val, BSTNode root) {
if (root == null) {
root = new BSTNode( new Interval(val, val) );
} else if (root.interval.start > val) {
root.left = addKey(val, root.left);
} else if (root.interval.end < val) {
root.right = addKey(val, root.right);
}
return root;
}
void inOrder(BSTNode root) {
if (root != null) {
inOrder(root.left);
list.add(root.interval);
inOrder(root.right);
}
}
/** Initialize your data structure here. */
BSTNode root;
List<Interval> list = new ArrayList();
public SummaryRanges() {
root = null;
}
public void addNum(int val) {
if (root == null) {
root = addKey(val, root);
} else {
if ( findKey(val, root) != null) return;
BSTNode left = findKey(val-1, root);
BSTNode right = findKey(val+1, root);
if (left == null && right == null) {
root = addKey(val, root);
} else if (left != null && right == null) {
left.interval.end++;
} else if (left == null && right != null) {
right.interval.start--;
} else {
Interval l = left.interval;
int e = right.interval.end;
root = remove(right.interval, root);
l.end = e;
}
}
}
public List<Interval> getIntervals() {
list.clear();
inOrder(root);
return list;
}
}