java: получить количество значений в пределах заданного диапазона ключей Guava Multimap

Question

У меня есть TreeMultimap<Integer, String>, который также включает в себя дубликаты ключей.

Я хочу, чтобы получить количества значений, которая находится в пределах определенного диапазона ключ , что тоже с O (LogN) временной сложностью.

Я попробовал сначала превращение TreeMultimap к SortedMap, используя свой метод asMap(), а затем создать в требуемом диапазоне в 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, вы должны иметь возможность обменять пространство на время.