java:获取Guava Multimap给定键范围内的值的计数

Question

我有一个TreeMultimap<Integer, String> ，其中还包括重复的键。

I want to get the count of values which lies within a specific key range, that too with O(logN) time complexity.

我尝试首先转换 TreeMultimap到 SortedMap通过使用其方法asMap()然后创建一个submap在所需的范围内并获取其大小。

SortedMap<Integer, Collection<String>> sortedMap = mapList.getTmm().asMap();
return sortedMap.subMap(beg,end).size();

复杂度是否为O(logN)？

另外，我在这里遇到了一个问题。当 TreeMultimap转换为SortedMap ，值是 Collection 的对象类(class)。即 TreeMultimap 中具有重复键的键值对包含在单个 Collection 中类(class)。所以方法size()返回错误的值。

还有其他方法可以实现这一目标吗？如有任何帮助，我们将不胜感激。

Answer 1

您可以尝试SortedMultiset ，它有一个范围查询的方法:

<强> subMultiset :

Returns a view of this multiset restricted to the range between lowerBound and upperBound.

示例代码:

import com.google.common.collect.*;

public class GuavaMultiMap {
    public static void main(String [] args) {
        Multimap<Integer, String> map = TreeMultimap.create();
        map.put(0, "-1");
        map.put(1, "a");
        map.put(1, "b");
        map.put(2, "c");
        map.put(2, "d");
        map.put(3, "e");

        SortedMultiset<Integer> keys = TreeMultiset.create();
        keys.addAll(map.keys());

        SortedMultiset<Integer> range = keys.subMultiset(1, BoundType.CLOSED, 3, BoundType.OPEN);
        System.out.println(range.size());
    }
}

输出: 4

上面的代码不会在 O(log(N)) 时间内运行，因为这一行 keys.addAll(...); 是 O( n)。但是，如果您将 SortedMultiset 与 Multimap 一起更新，您应该能够用空间换取时间。