どのデータ構造がキーと値のペアに対して効率的ですか？

Question

Key   value 
1-5   A 
7-10   B 
11-15   C 

入力が4の場合、出力A、入力8、出力Bなどです。 次のデータを格納するために使用できるデータ構造は、値を複数回保存しないでください。

私はHashMapを言ったが、それは効率的ではない。

P.S.私はインタビューで尋ねられました。

Answer 1

使用TreeMapです。次に、任意のキーのfloorKey()とceilingKey()のデータを検索し、両方の値が同じ場合はそれを返します。それ以外の場合はnullを返します。ここでの各クエリは、回答するのにO(log n)の時間が必要ですが、空間の複雑さは他のアプローチに比べて非常に少なくなります。ここでは、値がそれぞれintervalで一意であり、各キーに関連付けられている値が1つしかないと考えました。

TreeMap<Integer,String> map = new TreeMap<Integer,String>(); 

map.put(1,"A"); map.put(5,"A"); 
map.put(7,"B"); map.put(10,"B"); 
map.put(11,"C"); map.put(15,"C"); 

System.out.println(getData(4)); 
System.out.println(getData(6)); 

---

static String getData(int key) 
{ 
    Integer ceiling_key= map.ceilingKey(key); 
    Integer floor_key = map.floorKey(key); 

    if(ceiling_key == null || floor_key == null) 
     return null; 

    String value1 = map.get(ceiling_key); 
    String value2 = map.get(floor_key); 

    if(value1.equals(value2)) 
     return value1; 
    else 
     return null; 

} 

出力：

A 
null 

Answer 2

私はインタビュアーがあなたの場合は値

を持ついくつかのキーを保持することができますConcurrentNavigableMap

の答えを探していたと思う：

public static NavigableMap<Integer, String> map = new TreeMap<Integer, String>(); 
    static { 
     map.put(1, "A"); // 1..5 => A 
     map.put(6, null); // 6 => empty 
     map.put(7, "B"); // 7..10 => N 
     map.put(11, "C"); // 11..15 => C 
     map.put(16, null); // 16.. => empty 
    } 

をしてから

map.floorEntry(4).getValue() 

で値を取得します

Answer 3

キーが繰り返されないので、index of arrayを次のように使用できます。キー：

今

int[] array = {0,A,A,A,A,A,0,B,B,B,B,C,C,C,C,C,}; 

array[1] - array[5]での値Aとarray[7] - array[10] 値であり、キーが区間の終点であることで値を格納するためにB