Number Stream to Intervals
Implement a data structure with the following methods:
StreamSummary() constructs a new instance.
add(int val) adds the number val to the instance.
int[][] get() returns a sorted list of disjoint intervals summarizing the numbers we've seen so far.
Constraints
n ≤ 10,000 where n is the number of calls to add
m ≤ 10,000 where n is the number of calls to get
Example 1
Input
methods = ["constructor", "add", "add", "add", "add", "get"]
arguments = [[], [1], [3], [2], [9], []]`
Output
[None, None, None, None, None, [
[1, 3],
[9, 9]
]]
Explanation
s = StreamSummary()
s.add(1)
s.add(3)
s.add(2)
s.add(9)
s.get() == [[1, 3], [9, 9]]
Example 2
Input
methods = ["constructor", "add", "add", "add", "add", "get"]
arguments = [[], [1], [2], [4], [3], []]`
Output
[None, None, None, None, None, [
[1, 4]
]]
Explanation
s = StreamSummary()
s.add(1)
s.add(2)
s.add(4)
s.add(3)
s.get() == [[1, 4]]
- 哈希表
- 有序哈希表
- 二分法
这道题是给我们一个数据流。由于是流,因此不是一次性给我们的。题目的意思是每次 add 都会增加一个 [val, val] 的左右闭合的区间。如果 add 的区间与左边或者右边能够合并,我们需要将其合并,get 需要返回合并之后的区间总和。
以题目中的:
s.add(1)
s.add(3)
s.add(2)
s.add(9)
为例。
我们分步看一下合并后的区间情况。
s.add(1) # [ [1,1] ]
s.add(3) # [ [1,1], [3,3] ]
s.add(2) # [ [1,1], [2,2], [3,3] ] 可合并为 [ [1,3] ]
s.add(9) # [ [1,3], [9,9] ]
因此这个时候调用 get 会返回
[ [1,3], [9,9] ]
。题目意思就是这样,接下来我们只需要模拟即可。由于每次 add 都需要判断其是否会和前面的区间或者后面的区间进行合并,因此我们可以使用两个哈希表存储。
- 哈希表 start 其中 start[x] 表示以 x 为区间左端点的区间的右端点,也就是说其表示的是区间 [ x, start[x] ]。