如何在Java中的TreeSet中返回第k个元素 [英] How to return the kth element in TreeSet in Java

问题描述

也许我没有使用正确的数据结构。我需要使用一个集合，而且还要有效地返回第k个最小的元素。可以在Java中做TreeSet吗？似乎没有TreeSet的内置方法来执行此操作。

Maybe I am not using the right data structure. I need to use a set, but also want to efficiently return the kth smallest element. Can TreeSet in java do this? There seems no built-in method of TreeSet to do this.

请帮助我。

推荐答案

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

I don't believe that TreeSet has a method that directly does this. There are binary search trees that do support O(log n) random access (they are sometimes called order statistic trees), and there are Java implementations of this data structure available. These structures are typically implemented as binary search trees that store information in each node counting how many elements are to the left or right of the node, so a search down the tree can be made to find the appropriate element by descending into the appropriate subtree at each step. The classic "Introduction to Algorithms, Third Edition" book by Cormen, Rivest, Leisserson, and Stein explores this data structure in their chapter "Augmenting Data Structures" if you are curious how to implement one yourself.

或者，您可能（在某些情况下）可以使用 TreeSet 的 tailSet 方法并修改二进制搜索以尝试找到第k个元素。具体来说，查看 TreeSet 的第一个和最后一个元素，然后（如果可能的话给出内容），选择两个中间的元素，并将其作为参数传递给 tailSet 可以在中点之后获取集合元素的视图。使用 tailSet 中的元素数量，您可以决定是否找到该元素，还是探索树的左半部或右半部分。这是在树上略微修改的插值搜索，并且可能会很快。然而，我不知道 tailSet 方法的内部复杂性，所以这可能实际上比订单统计树更差。如果您无法计算两个元素的中点，也可能会失败，例如，如果您将 TreeSet 中存储 / code>。

Alternatively, you may be able (in some cases) to use the TreeSet's tailSet method and a modified binary search to try to find the kth element.  Specifically, look at the first and last elements of the TreeSet, then (if possible given the contents) pick some element that is halfway between the two and pass it as an argument to tailSet to get a view of the elements of the set after the midpoint. Using the number of elements in the tailSet, you could then decide whether you've found the element, or whether to explore the left or right halves of the tree. This is a slightly modified interpolation search over the tree, and could potentially be fast. However, I don't know the internal complexity of the tailSet methods, so this could be actually be worse than the order statistic tree. It also might fail if you can't compute the "midpoint" of two elements, for example, if you are storing Strings in your TreeSet.

希望这有帮助！

这篇关于如何在Java中的TreeSet中返回第k个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！