java - TreeSet:有效地元素数量小于某个值

Question

我需要一种方法来非常快速地计算整数 TreeSet 中小于 X 的元素数量。

我可以使用

• 子集()
• headSet()
• tailSet()

方法，但它们真的很慢(我只需要计数，而不是数字本身)。有办法吗？

谢谢。

<小时/>

编辑:

我找到了一种解决方法，可以让事情变得更快!我正在使用 BitSet 和它的 cardinality() 方法。我首先创建一个 BitSet，对于添加到 TreeSet 的每个元素，我在 BitSet 中设置相应的索引。现在，要计算小于 X 的元素数量，我使用:

bitset.get(0, X+1).cardinality()

与 treeset.subSet(0, true, X, true).size() 相比，这要快得多。

有人知道为什么吗？我假设 BitSet.cardinality() 不使用线性搜索。

Answer 1

由于到目前为止所有答案都指向与 Java 的 TreeSet 不同的数据结构，我建议使用 Fenwick 树，它的更新和查询时间复杂度为 O(log(N))；请参阅link用于 Java 实现。