如何在Java的TreeSet中返回第k个元素？

我不相信有直接做到这一点的方法。有一些二叉搜索树确实支持O（log n）随机访问（它们有时被称为顺序统计树），并且有此数据结构的Java实现可用。这些结构通常实现为二叉搜索树，在每个节点中存储信息，计算节点左侧或右侧有多少个元素，因此可以通过在每个步骤中下降到相应的子树来向下搜索树以找到适当的元素。Cormen，Rivest，Leisserson和Stein的经典“算法导论，第三版”一书在他们的“增强数据结构”一章中探讨了这种数据结构，如果你很好奇如何自己实现一个。TreeSet

或者，您可以（在某些情况下）使用 tailSet 方法和修改后的二进制搜索来尝试查找第 k 个元素。具体来说，查看 的第一个和最后一个元素，然后（如果可能的话，给定内容）选择一些介于两者之间的元素，并将其作为参数传递给中点之后的集合元素。然后，使用 中的元素数，您可以决定是否找到了该元素，或者是浏览树的左半部分还是右半部分。这是对树的略微修改的插值搜索，可能会很快。但是，我不知道这些方法的内部复杂性，因此这实际上可能比订单统计树更糟糕。如果无法计算两个元素的“中点”（例如，如果将 s 存储在 .TreeSetTreeSettailSettailSettailSetStringTreeSet

您只需要迭代到元素 k。一种方法是使用Guava的Iterables.get方法之一：

T element = Iterables.get(set, k);

没有内置的方法可以执行此操作，因为 a 不是基于索引的操作，因此通常为 s 保留。A 更适合于查找最接近的包含元素，该元素> = 某个值。SetListListTreeSet

如果对第 k 个最小元素的最快访问确实很重要，那么您可以做的一件事就是使用 a 而不是 a，并通过二进制搜索插入点来处理插入，然后在该索引处插入元素或替换该索引处的现有元素，具体取决于搜索结果。然后你可以通过调用来获得O（1）中的第k个最小元素。ArrayListTreeSetget(k)

您甚至可以创建一个处理所有这些的实现，并根据需要添加该方法。SortedSetget(index)