TreeSet中过滤方法的时间复杂度

Question

val x = TreeSet<Int>(compareBy { it.toString() })
x.add(2);
x.add(4)
x.add(5)
x.add(15)
x.add(1)
x.add(34)
println(x)
print(x.filter { it in 5..19 })

我有一些类似于上面提到的示例代码的用例。我有一堆数据(大小可能相当大)考虑一个时间序列，我需要从列表中过滤掉那些介于2个日期之间的项目?有没有比O(n)方法更好的解决方案?

Answer 1

这里的问题是您的TreeSet的排序顺序与范围的顺序不同，因此我们不能在TreeSet中找到范围边界并取两者之间的所有值。

如果TreeSet是按自然顺序排序的(val x = TreeSet<Int>())，你可以这样做:

val subset = x.subSet(5, true, 19, true)

这个操作几乎是免费的(O(1))，你只需要支付(O(log(N))来遍历这个TreeSet(迭代器构造将需要两次查找子集边界)。

之后，你可以用不同的方式进行排序:

println(subset.toSortedSet(compareBy { it.toString() }))