如何使用二进制搜索从排序的TreeSet中检索元素？

Question

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

下面是我的代码，我在我的一个方法中传递列表，并将它们合并到一起。TreeSet 为了避免重复... 内的所有列表 inputs 排序 -

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中提取一个元素？我想找到一个元素 x 在那 TreeSet如果存在，则返回，如果不存在，则返回下一个最大的数值 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
    }
}

Answer 1

TreeSet 是由一个 NavigableMap, a TreeMap 特别是。调用 contains() 关于 TreeSet 代表们 TreeMap.containsKey()，这是一个二进制搜索的实现。

你可以通过使用 TreeSet.contains()但你必须先拥有对象。如果你想能够查找和检索一个对象，那么一个叫做 Map 的实现会更好。

Answer 2

TreeSet，其本质是一个 分类集 并使用 红树黑树 通过TreeMap作为它的后盾

基本上是这样的 TreeSet.add(E) -> TreeMap.put(E,NULL);

因为它已经是一个二进制的、排序的树结构 任何 "get "或 "contains "都会导致O(log n)操作。

但你的代码和你的问题并不一致。

你在扁平化一个 List<List<Integer>> 并把它们全部放进去就可以得到所有唯一的元素（至少，这段代码会这么做）。

但你下面的方法却说 "给定这个整数，给我一个 List<Integer>"，这在上面的代码中是无法实现的。

那么，让我来依次回答你的问题。

1. 当然，是的
2. 不，你误解了Set(你不能通过设计来提取)，如果你能做到Set.contains(e)，那么你就有了元素，不需要提取任何东西。

如果你需要做一些类似于 "集合提取 "的事情，那么就使用TreeMap，或者将你的集合转回列表，然后进行 myList.get(Collections.binarySearch(myElement));

Answer 3

你可以使用TreeSet.floor()，它根据 文献

返回该集合中小于或等于给定元素的最大元素，如果没有该元素，则返回空值。