Java的TreeSet.floor和TreeSet.ceiling的.NET等效方法是什么？

Question

作为一个例子，有一棵二叉搜索树，其中包含一系列数值。在添加新的数值之前，我需要检查它是否已经包含了“几乎重复”的数值。我有一个Java解决方案，简单地执行floor和ceiling，并进一步使用条件来完成这个任务。

JAVA: 给定一个TreeSet，floor()返回此集合中小于或等于给定元素的最大元素；ceiling()返回此集合中大于或等于给定元素的最小元素。

TreeSet<Long> set = new TreeSet<>();

long l = (long)1;  // anything
Long floor = set.floor(l);
Long ceil = set.ceiling(l);

C#: 最接近的数据结构似乎是 SortedSet<>。请问有什么建议的方法可以获得输入值的 floor 和 ceil 结果？

SortedSet<long> set = new SortedSet<long>();

- user2376997

---

可能是 Math.Floor 和 Math.Ceiling。但是 l 是什么呢？ - SᴇM

@SeM，我需要在BST范围上操作的floor和ceiling方法。 - user2376997

在 .Net 中非常需要这个。如果不编写自己的数据结构，就无法实现各种算法。 - koolaang

Answer 1

如上所述，这不是答案，因为我们期望树的时间复杂度是对数级别的。Java的floor和ceiling方法是对数级别的。GetViewBetween是对数级别的，Max和Min也是对数级别的，因此：

对于SortedSet<long>，使用以下公式来获取floor： sortedSet.GetViewBetween(long.MinValue, num).Max 对于SortedSet<long>，使用以下公式来获取ceiling： sortedSet.GetViewBetween(num, long.MaxValue).Min。

"Original Answer"翻译成中文为"最初的回答"。

- Lucio Silveira

---

由于GetViewBetween()方法返回的是包含Count属性的SortedSet，该属性需要O(N)时间来配置，因此该方法无法实现对数时间复杂度。 - wkwk

遗憾的是，GetViewBetween() 的时间复杂度为 O(N)。 - Ojas Maru

虽然根据一些评论，GetViewBetween()可能是O(logN)，但代码本身是否有问题呢？sortedSet.GetViewBetween(num, long.MaxValue).Min就是num本身。 - chuang

@chuang 如果 num 不在 sortedSet 中则不会执行。在我看来，该代码是正确的。这里有些评论说 dotnet core 的 GetViewBetween 是 O(logN) 的（与您的观点相同，只是在这个问题上没有看到这样的评论）：https://dev59.com/82kw5IYBdhLWcg3wfKrZ - Millie Smith

Answer 2

您可以使用类似以下的方法。在 Linq 中有 LastOrDefault 方法：

var floor = sortedSet.LastOrDefault(i => i < num);
// num is the number whose floor is to be calculated
if (! (floor < sortedSet.ElementAt(0)))
{
  // we have a floor
}
else
 // nothing is smaller in the set
{
}

- Gauravsa

---

这个解决方案不会像Java的解决方案那样具有很好的对数时间复杂度，对吧？它只是一个线性搜索。 - Lukáš Lánský

是的，我同意。我认为搜索是二进制的，具有O(n)的复杂度..在C#中使用SortedSet与在Java中使用TreeSet将会成为一个很好的SO问题。 - Gauravsa