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

问题描述

也许我没有使用正确的数据结构。我需要使用一组，也希望有效地返回第k个最小元素。可以TreeSet的在Java中做到这一点？似乎没有内置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的有直接做到这一点的方法。有迹象表明，这样做支持Ø二叉搜索树（log n）的随机访问（有时被称为顺序统计树），并有<一href="https://web.archive.org/web/20090202173819/http://classes.engr.oregonstate.edu/eecs/winter2005/cs325/clrs2e/OrderStatisticTree.java"相对=nofollow> Java的这种数据结构可用的实现。这些结构通常实现为将信息存储在每个节点计数有多少个元素的节点的左或右二叉搜索树，所以搜索下来树可通过降入在适当的子树，找到适当的元素每个步骤。经典的算法导论，第三版书Cormen，维斯特，Leisserson，和斯坦因在其章的增广数据结构，如果你是好奇，如何自己实现一个探讨这个数据结构。

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的。

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.

希望这有助于！

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