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

Question

我正在尝试将多个排序列表合并到一个 TreeSet 中。

下面是我的代码，其中我在我的一种方法中传递列表列表并将它们组合在一起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。

或者与我目前使用的数据结构相比，我更适合使用另一种数据结构吗？

更新代码：-

私有树集树 = 新树集（）；

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由 a 支持NavigableMap，TreeMap特别是a 。调用contains()一个TreeSet代表来TreeMap.containsKey()，这是一个二进制搜索实现。

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