Java 如何使用二分搜索从排序的 TreeSet 中检索元素？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22078377/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to retrieve elements from sorted TreeSet using Binary Search?
提问by
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 TreeSetto avoid duplicacy... All the lists inside inputsare sorted -
下面是我的代码，其中我在我的一种方法中传递列表列表并将它们组合在一起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)
}
- 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
xin thatTreeSet, if it is there, then return it, if it is not there then return the next largest value from theTreeSet.
- 首先，这是将多个排序列表合并到 TreeSet 中的正确方法吗？有没有什么直接的方法可以有效地合并 TreeSet 中的多个排序列表？
- 其次，我将如何以 O(log n) 的时间复杂度从该 TreeSet 中提取一个元素？我想找到的元素
x在TreeSet，如果有，则返回它，如果它不存在则返回从下一个最大的价值TreeSet。
Or may be I am better off to another data structure as compared to which I am using currently?
或者与我目前使用的数据结构相比，我更适合使用另一种数据结构吗？
UPDATED CODE:-
更新代码：-
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
}
}
采纳答案by Mike B
TreeSetis backed by a NavigableMap, a TreeMapspecifically. Calling contains()on a TreeSetdelegates to TreeMap.containsKey(), which is a binary search implementation.
TreeSet由 a 支持NavigableMap，TreeMap特别是a 。调用contains()一个TreeSet代表来TreeMap.containsKey()，这是一个二进制搜索实现。
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 Mapimplementation will be better.
您可以使用 来检查对象是否包含在集合中TreeSet.contains()，但您必须先拥有该对象。如果您希望能够查找和检索对象，那么Map实现会更好。
回答by Christian Bongiorno
TreeSet, by it's nature is a sorted setand uses a red-tree-black-treevia TreeMap as it's backing
TreeSet，本质上是一个排序集，并通过 TreeMap使用红树黑树作为它的支持
Basically: TreeSet.add(E) -> TreeMap.put(E,NULL);
基本上： TreeSet.add(E) -> TreeMap.put(E,NULL);
As it is already a binary, sorted tree structure any 'get' or 'contains' will result in an O(log n) operation.
由于它已经是一个二元排序树结构，任何“获取”或“包含”都将导致 O(log n) 操作。
Your code and your question though don't line up.
你的代码和你的问题虽然没有对齐。
You're flattening a List<List<Integer>>and just putting them all in to get all unique elements (or, at least, that's what this code will do).
您正在展平 aList<List<Integer>>并将它们全部放入以获得所有唯一元素（或者，至少，这就是此代码将要做的）。
But then your following method says "given this integer, give me a List<Integer>" which isn't achievable in the above code
但是随后您的以下方法说“给定这个整数，给我一个List<Integer>”，这在上面的代码中是无法实现的
So, let me answer your questions in order:
那么，让我按顺序回答您的问题：
- Sure/Yes Y
- No. You misunderstand Sets (you can't extract by design) If you can do Set.contains(e) then you HAVE the element and need not extract anything
- 确定/是 Y
- 不。你误解了集合（你不能按设计提取）如果你可以做 Set.contains(e) 那么你有元素并且不需要提取任何东西
If you need to do something like a "Set extraction" then use a TreeMap or turn your set back into a list and do myList.get(Collections.binarySearch(myElement));
如果您需要执行诸如“集合提取”之类的操作，请使用 TreeMap 或将您的集合重新转换为列表并执行 myList.get(Collections.binarySearch(myElement));
