如何在Java中的TreeSet中返回第k个元素？ [英] How to return the k-th 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 k-th 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 ' s tailSet 方法和经过修改的二进制搜索以尝试找到第k个元素。具体来说，查看 TreeSet 的第一个和最后一个元素，然后（如果可能，给定内容）选择一个介于两者中间的元素，并将其作为参数传递给 tailSet 可以在中点之后查看集合中的元素。然后，使用 tailSet 中的元素数量，可以决定是否找到了该元素，还是探索树的左半部分或右半部分。这是对树的插值搜索的略微修改，并且可能很快。但是，我不知道 tailSet 方法的内部复杂性，因此这实际上可能比顺序统计树还差。如果您无法计算中点值，也可能会失败。例如，如果要将 String s存储在 TreeSet 中。

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屋！