哪個數據結構對鍵值對有效？

-1

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

如果輸入爲4，輸出A，輸入爲8，輸出爲B等等。我可以使用哪種數據結構來存儲以下數據，以便您不應多次存儲值。哪個數據結構對鍵值對有效？

我說的是HashMap，但效率不高。

P.S.我在採訪中被問到。

來源

2017-06-21 Hitesh Vaghani

如果它的許可，您可以交換密鑰和值，然後用A，B，C爲鍵和存儲值列表/設置你的hashmap中的對象，你有1-5,7-10,11-15的值;雖然這不會有效，但它可能在這裏起到作用。 – srp321

我知道OP來自哪裏。面試官有時真的很有意思，很少提供解釋他們自己的問題和反駁。 –

BST根據最小數量進行索引，併爲每個節點保存最大值和值。搜索小於或等於您要查找的號碼的最小值，查看最大值是否大於或等於您的號碼。 – dave

使用TreeMap的值存儲與鍵爲間隔的結束點。然後檢索任何鍵的floorKey()和ceilingKey()的數據，並且如果兩個值相同，則返回它，否則返回null。這裏的每個查詢都需要O(log n)時間來回答，但與其他方法相比，空間複雜度非常低。在這裏，我認爲每個interval的值都是唯一的，每個鍵只有一個值與它關聯。

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

來源

2017-06-21 05:34:32

完美，謝謝@sanket –

我覺得面試官在尋找的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()

值

來源

2017-06-21 05:25:01 user7294900

Intersting實現，但請注意，您需要使用'NavigableMap.floorEntry'將值作爲「範圍」而不是'Map.get'。順便說一句，多挖一點，這是來自'TreeMap'實現的'NavigableMap'的一個特性，不需要使用特定的類。 – AxelH

更新的解決方案。面試問題似乎要問一個關鍵的範圍 – user7294900

@ user7294900不錯的一個。謝謝 –

由於鍵不重複，你可以使用數組的索引作爲關鍵：

在 array[1] - array[5]

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

現在還有價值A和array[7] - array[10] 值B

來源

2017-06-21 05:27:52

不能使用這個，多次存儲值是不允許的。 –

哪個數據結構對鍵值對有效？

回答

相關問題