java：Guava Multimapの特定のキー範囲内の値の数を取得

Question

私はTreeMultimap<Integer, String>を持っています。これには重複キーも含まれています。

私もO（logN個）時間複雑であること、特定のキー の範囲内にある値の数を取得したいです。

Iは最初にその方法asMap()を使用し、必要な範囲でsubmapを作成し、そのサイズをフェッチすることによってSortedMapからTreeMultimapを変換してみました。

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を：

は下界とは、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()); 
    } 
} 

出力：この行keys.addAll(...);がO(n)あるので4

上記のコードはO(log(N))時間で動作しません。ただし、SortedMultisetをMultimapと一緒に更新しておくと、時間の交換が可能になります。