数据结构

Question

有一个大的数字流进来，比如5 6 7 2 3 1 2 3 ..考虑到元素必须以降序插入并且应该消除重复的约束，哪种类型的数据结构适合于这个问题。

我没有寻找任何代码，只是想法？我在想一个自平衡的BST，我们可以添加这样的条件，即所有节点<当前节点在左侧，所有节点>当前节点在右侧，这样可以处理重复的节点。但我不认为它们必须以降序插入。有没有更好的选择..当然，它需要在时间和空间上都是有效的。

Answer 1

这在一定程度上取决于重复项与总样本大小的比率。

高重复比率可能更容易解决，或者只使用散列(其键偶尔被排序到有序列表中)，或者使用散列和空白树的组合(用于过滤重复的散列)。

低重复比，只需按照您的建议使用平衡树即可。

Answer 2

既然您已经获得了仅仅是数字的简单数据，为什么不使用存储在数组中的二进制堆呢？当然，您应该知道元素数量的上限，以避免重新分配它。