Scala 树集 takeRight

Question

我有一大组整数，我正在使用 TreeSet 来存储它们。我的任务是找出小于输入数字的两个数字。

例如 Set(1, 5, 8, 9) 和 input = 6 应该 return (1, 5) 输入 = 8 应该 return (5, 8)

到目前为止，我的代码如下：

treeSet.to(inputNumber).takeRight(2)

我的理解是 .to() return 是元素的投影，少于 logN 时间的输入。我想知道额外的 takeRight 的复杂性是什么。我无法从文档中找出答案。

由于我的输入列表有数百万个数字，因此我正在努力使其尽可能高效。

Answer 1

有时甚至在查看文档之前先查看源代码会更容易。

在TreeSet中：

override def takeRight(n: Int) = drop(size - math.max(n, 0))

override def drop(n: Int) = {
  if (n <= 0) this
  else if (n >= size) empty
  else newSet(RB.drop(tree, n))
}

在RedBlackTree中：

def drop[A: Ordering, B](tree: Tree[A, B], n: Int): Tree[A, B] = blacken(doDrop(tree, n))

RBtree中的删除是O(log n)，所以Scala的TreeSet中的takeRight也是O(log n).

Scala 树集 takeRight

Scala TreeSet takeRight

scala

treeset

data-structures