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.

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

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

它是否具有复杂性 O(logN)？

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

还有其他方法可以实现吗？感谢任何帮助。

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 一起更新，您应该能够用 space 换取时间。

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

java: get count of values within a given key range of Guava Multimap

java

dictionary

multimap

sortedmap

guava