java - 如何从连续运行的随机整数生成器中(有效地)找到整数簇的数量？

Question

有一个随机整数生成器，它生成随机整数并在后台运行。需求设计一个API，调用时返回当时的簇数。

簇:簇是连续整数的字典顺序。例如，在这种情况下，10,7,1,2,8,5,9 簇是 3 (1,2--5--7,8,9,10)。

当有数十亿或数万亿的整数时，如何解决这个问题。什么可能是最佳解决方案？ (请记住，生成器在后台运行，可以随时多次调用 API)

我的方法:不断将生成器中的整数插入到列表中。当调用 API 时，对列表进行排序(插入)，并遍历它以找到聚类数。但我认为这不是一种有效的方法。

Answer 1

某种区间树怎么样。不是标准的，它可以跟踪重叠的间隔，而是一种更简单的，它只跟踪不相交的间隔并自动合并重叠/相邻的间隔。

所以一个 BST 区间，按开始排序。要插入一个新的间隔，

1. 找到最高小于新区间起点的值，如果相邻则将其加入
2. 采用您现在拥有的间隔(您要插入的间隔或连接的间隔)并找到最低 - 高于 - 其终点，如果相邻则加入它们。
3. 如果您加入了两次，请移除第一个(较短的)加入间隔。
4. 如果加入了零次，则插入新的区间作为新节点
5. 如有必要，应用通常的 BST 平衡旋转以保持树至少在一定程度上平衡

在任何时候，簇的数量就是叶子的数量。您甚至不必显式计算它们，只需在更改树时更新计数即可。

Insert 的簇数是对数的，它们的大小无关紧要。这有一个有趣的副作用，对于随机整数，这会变慢一段时间，因为树必须代表大部分单位间隔，但是当足够多的整数在那里时，它会慢慢开始再次变快，因为超过某个点插入会倾向于加入比他们创造的更多的间隔。最终，对于树中的每个整数，它只剩下一个节点，代表跨越所有整数的单个集群。