我正试图将多个排序列表合并到一个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)
}
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
}
}
TreeSet
是由一个 NavigableMap
, a TreeMap
特别是。调用 contains()
关于 TreeSet
代表们 TreeMap.containsKey()
,这是一个二进制搜索的实现。
你可以通过使用 TreeSet.contains()
但你必须先拥有对象。如果你想能够查找和检索一个对象,那么一个叫做 Map
的实现会更好。
TreeSet,其本质是一个 分类集 并使用 红树黑树 通过TreeMap作为它的后盾
基本上是这样的 TreeSet.add(E) -> TreeMap.put(E,NULL);
因为它已经是一个二进制的、排序的树结构 任何 "get "或 "contains "都会导致O(log n)操作。
但你的代码和你的问题并不一致。
你在扁平化一个 List<List<Integer>>
并把它们全部放进去就可以得到所有唯一的元素(至少,这段代码会这么做)。
但你下面的方法却说 "给定这个整数,给我一个 List<Integer>
",这在上面的代码中是无法实现的。
那么,让我来依次回答你的问题。
如果你需要做一些类似于 "集合提取 "的事情,那么就使用TreeMap,或者将你的集合转回列表,然后进行 myList.get(Collections.binarySearch(myElement));
你可以使用TreeSet.floor(),它根据 文献
返回该集合中小于或等于给定元素的最大元素,如果没有该元素,则返回空值。