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

Question

我有一个TreeMultimap<Integer, String>，它也包含重复的键。

我想获得值的计数，它位于一个特定的键 0 (logN)时间复杂度

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

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

它的复杂度是否O(logN)?

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

还有其他方法可以实现这个吗?

Answer 1

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

subMultiset:

返回被限制在lowerBound和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一起更新，则应该能够用空间换取时间。