我需要一种方法来非常快速地计算整数 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() 不使用线性搜索。
最佳答案
由于到目前为止所有答案都指向与 Java 的 TreeSet 不同的数据结构,我建议使用 Fenwick 树,它的更新和查询时间复杂度为 O(log(N));请参阅link用于 Java 实现。
关于java - TreeSet:有效地元素数量小于某个值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34427758/