如何使用二进制搜索从已排序的TreeSet中检索元素？ [英] How to retrieve elements from sorted TreeSet using Binary Search?

问题描述

我正在尝试将多个排序列表合并到一个TreeSet中。然后我想在该TreeSet上应用二进制搜索算法来检索O（log n）时间复杂度中的元素。

I am trying to merge multiple sorted lists into one TreeSet.. And then I am thinking to apply Binary Search algorithm on that TreeSet to retrieve the element in O(log n) time complexity..

下面是我的代码，我在其中一个方法中传递列表列表并将它们组合到 TreeSet 中以避免重复... 输入内的所有列表都已排序 -

Below is my code in which I am passing List of Lists in in one of my method and combining them into TreeSet to avoid duplicacy... All the lists inside inputs are sorted -

private TreeSet<Integer> tree = new TreeSet<Integer>();

public void mergeMultipleLists(final List<List<Integer>> inputs) {
    tree = new TreeSet<Integer>();
    for (List<Integer> input : inputs) {
        for(Integer ii : input) {
            tree.add(ii);
        }
    }
}

public List<Integer> getItem(final Integer x) {
    // extract elements from TreeSet in O(log n)
}

• 首先，这是将多个排序列表合并到TreeSet中的正确方法吗？有没有直接的方法可以有效地合并TreeSet中的多个排序列表？


• 其次，如何从O（log n）时间复杂度中提取该TreeSet中的元素？我想在 TreeSet 中找到一个元素 x ，如果它在那里，然后返回它，如果它是然后不返回 TreeSet中的下一个最大值。


• First of all, is this right way to merge multiple sorted lists into TreeSet? Is there any direct way to merge multiple sorted lists in TreeSet efficiently?
• Secondly, how would I extract an element from that TreeSet in O(log n) time complexity? I would like to find an element x in that TreeSet, if it is there, then return it, if it is not there then return the next largest value from the TreeSet.

或者可能与我目前使用的数据结构相比，我是否更适合其他数据结构？

Or may be I am better off to another data structure as compared to which I am using currently?

更新后的代码： -

private TreeSet tree = new TreeSet（）;

private TreeSet tree = new TreeSet();

public SearchItem(final List<List<Integer>> inputs) {
    tree = new TreeSet<Integer>();
    for (List<Integer> input : inputs) {
        tree.addAll(input);
    }
}

public Integer getItem(final Integer x) {
    if(tree.contains(x)) {
        return x;
    } else {
        // now how do I extract next largest 
         // element from it if x is not present
    }
}




推荐答案

TreeSet 支持一个 NavigableMap ，一个 TreeMap 。在 TreeSet 上调用包含（）委托给 TreeMap.containsKey（），这是一个二进制搜索实现。

TreeSet is backed by a NavigableMap, a TreeMap specifically. Calling contains() on a TreeSet delegates to TreeMap.containsKey(), which is a binary search implementation.

您可以使用 TreeSet.contains（）检查集合中是否包含对象，但你必须先拥有该对象。如果您希望能够查找和检索对象，那么 Map 实现将会更好。

You can check if an object is contained in the set by using TreeSet.contains(), but you have to have the object first. If you want to be able to look up and retrieve an object, then a Map implementation will be better.

这篇关于如何使用二进制搜索从已排序的TreeSet中检索元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！