如何在Java中返回TreeSet中的第k个元素
也许我没有使用正确的数据结构。 我需要使用一个集合，但也希望有效地返回第k个最小元素。 可以在Java中使用TreeSet吗？ 似乎没有TreeSet的内置方法来执行此操作。
请帮帮我。
我不相信TreeSet有一个直接执行此操作的方法。 有二叉搜索树支持O（log n）随机访问（它们有时称为顺序统计树 ），并且可以使用此数据结构的Java实现 。 这些结构通常实现为二进制搜索树，它在每个节点中存储信息，计算节点左侧或右侧有多少元素，因此可以通过下移到适当的子树来查找树中的相应元素。每一步。 Cormen，Rivest，Leisserson和Stein的经典“算法导论，第三版”一书在他们的“增加数据结构”一章中讨论了这个数据结构，如果你很好奇如何自己实现它。
或者，您可以（在某些情况下）使用TreeSet的tailSet方法和修改的二进制搜索来尝试查找第k个元素。 具体来说，查看TreeSet的第一个和最后一个元素，然后（如果可能的话给出内容）选择一些介于两者之间的元素并将其作为参数传递给tailSet以获取后面的集合元素的视图中点。 使用tailSet的元素数量，您可以决定是否找到了元素，或者是否要探索树的左半部分或右半部分。 这是对树的略微修改的插值搜索 ，并且可能很快。 但是，我不知道tailSet方法的内部复杂性，所以这实际上可能比订单统计树更糟糕。 如果无法计算两个元素的“中点”，也可能会失败，例如，如果要在TreeSet中存储String 。
希望这可以帮助！
你只需要迭代到元素k 。 一种方法是使用Guava的Iterables.get方法之一：
T element = Iterables.get(set, k);
没有内置方法来执行此操作，因为Set不是List而像这样的基于索引的操作通常是为List s保留的。 TreeSet更适合于查找最接近的包含元素> =某个值的内容。
如果对第k个最小元素的最快可能访问非常重要，那么你可以做的一件事就是使用ArrayList而不是TreeSet并通过二进制搜索插入点来处理插入，并将元素插入该索引或替换现有的该索引处的元素，具体取决于搜索结果。 然后你可以通过调用get(k) O（1）中的第k个最小元素。
你甚至可以创建一个SortedSet实现来处理所有这些，并添加get(index)方法，如果你真的想要的话。
使用TreeSet.iterator（）按升序获取迭代器并调用next() K次：
// Example for Integers Iterator it = treeSet.iterator(); int i = 0; Integer current = null; while(it.hasNext() && i < k) { current = it.next(); i++; }
我有同样的问题。 所以我拿了java.util.TreeMap的源代码并编写了IndexedTreeMap 。 它实现了我自己的IndexedNavigableMap ：
public interface IndexedNavigableMap extends NavigableMap { K exactKey(int index); Entry exactEntry(int index); int keyIndex(K k); }
该实现基于在更改时更新红黑树中的节点权重。 权重是给定节点下的子节点数加一个自身。 例如，当树向左旋转时：
private void rotateLeft(Entry p) { if (p != null) { Entry r = p.right; int delta = getWeight(r.left) - getWeight(p.right); p.right = r.left; p.updateWeight(delta); if (r.left != null) { r.left.parent = p; } r.parent = p.parent; if (p.parent == null) { root = r; } else if (p.parent.left == p) { delta = getWeight(r) - getWeight(p.parent.left); p.parent.left = r; p.parent.updateWeight(delta); } else { delta = getWeight(r) - getWeight(p.parent.right); p.parent.right = r; p.parent.updateWeight(delta); } delta = getWeight(p) - getWeight(r.left); r.left = p; r.updateWeight(delta); p.parent = r; } }
updateWeight只是更新权重到根：
void updateWeight(int delta) { weight += delta; Entry p = parent; while (p != null) { p.weight += delta; p = p.parent; } }
当我们需要通过索引找到元素时，这是使用权重的实现：
public K exactKey(int index) { if (index < 0 || index > size() - 1) { throw new ArrayIndexOutOfBoundsException(); } return getExactKey(root, index); } private K getExactKey(Entry e, int index) { if (e.left == null && index == 0) { return e.key; } if (e.left == null && e.right == null) { return e.key; } if (e.left != null && e.left.weight > index) { return getExactKey(e.left, index); } if (e.left != null && e.left.weight == index) { return e.key; } return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1); }
还可以非常方便地找到键的索引：
public int keyIndex(K key) { if (key == null) { throw new NullPointerException(); } Entry e = getEntry(key); if (e == null) { throw new NullPointerException(); } if (e == root) { return getWeight(e) - getWeight(e.right) - 1;//index to return } int index = 0; int cmp; if (e.left != null) { index += getWeight(e.left); } Entry p = e.parent; // split comparator and comparable paths Comparator cpr = comparator; if (cpr != null) { while (p != null) { cmp = cpr.compare(key, p.key); if (cmp > 0) { index += getWeight(p.left) + 1; } p = p.parent; } } else { Comparable k = (Comparable) key; while (p != null) { if (k.compareTo(p.key) > 0) { index += getWeight(p.left) + 1; } p = p.parent; } } return index; }
您可以在http://code.google.com/p/indexed-tree-map/找到此工作的结果。 已移至https://github.com/geniot/indexed-tree-map
[下面，我将“第k个最小元素搜索操作”缩写为“ Kth op。”]
你需要提供更多细节。 您的数据结构将提供哪些操作？ 与N相比， Kth操作中的K非常小，还是可以是任何东西？ 与查找相比，您多久会进行一次插入和删除？ 与查找相比，您多久会进行一次Kth最小元素搜索？ 您是否正在寻找Java库中几行的快速解决方案，或者您是否愿意花费一些精力来构建自定义数据结构？
要提供的操作可以是以下任何子集：
-
LookUp （通过键找到一个元素;其中key是可比较的，可以是任何东西）
-
插入
-
删除
-
第K
以下是一些可能性：
-
如果没有/很少插入和删除，您可以只对元素进行排序并使用数组，其中O（Log（N））查找时间， O（1）表示Kth 。
-
如果O（Log（N））为LookUp ，则插入 ， 删除和O（k）为Kth op。 足够好，可能最简单的实现是Skip Lists。 （如果您需要更多细节，维基百科文章非常好）
-
如果K足够小，或者Kth操作仅在“插入和删除阶段”之后，您可以将最小的K元素保留在堆中，在O（N + k Log k）时间的插入和删除之后进行排序。 （你还需要一个单独的Hash for LookUp ）
-
如果K是任意的并且O（N）足够用于Kth操作，则可以使用Hash进行O（1）时间查找，并使用“单侧QuickSort”算法进行Kth操作（基本思想是做一个快速排序，但在每个二进制除法上仅在你真正需要的一侧递归;这将给出（这是一个粗略的简化） N（1/2 + 1/4 + 1/8 + …）= O（N）预期时间）
-
您可以构建一个增强的“简单”间隔树结构，每个节点保持其子节点的数量，以便LookUp ， Insert ， Delete ， Kth都可以在O（Log N）时间内计算，只要树是平衡的，但也许它会如果你是新手，不难实施。
等等。作为您问题的可能解释，这组备选方案是无限的。
你能使用ConcurrentSkipListSet并使用toArray（）方法吗？ ConcurrentSkipListSet按元素的自然顺序排序。 我唯一不确定的是，如果toArray（）是O（n），或者它是由List支持（由数组支持，如ArrayList），它是O（1）。
如果toArray（）是O（1），你应该能够成为skipList.toArray（）[k]来获得第k个最小元素。
我知道这个问题很老，但是由于TreeSet实现了NavigableSet，你可以访问在常量时间运行的subSet方法。
subSet(k, k + 1).first();
first（）调用采用log（n）时间，其中n是原始集的大小。 这确实创建了一些不必要的对象，可以通过更强大的TreeSet实现来避免，但它避免使用第三方库。