匹配值最接近值範圍內以最簡單的

我遇到了，我需要一些幫助，一個問題 - 假設我有包括鍵（整數）和值（整數和）一些數據集。我需要能夠給定一個鍵的一些值，發現最小範圍的關鍵其所屬（即，尋找最近的較大和較小的鍵），然後通過插值返回的匹配值。我想知道哪種方式可以讓我在最快的時間內完成這個任務（空間複雜性問題要小得多）。同時，刪除是無關緊要的，所有值都在啓動時（我們可以假設會有啓動後不再添加值）給出。我的重點是搜索時間，而不是插入。匹配值最接近值範圍內以最簡單的

最基本的解決方案將是，以保持鍵的排序後的數組，並在其上使用二進制搜索 - 直到我找到輸入鍵或發現其比輸入鍵較大和較小兩個相鄰元件。這個選項需要O（log n）來插入和搜索。我想知道有沒有更好的。

謝謝！

來源

2012-08-22 Gilad B

我會用的NavigableMap如TreeMap的。

NavigableMap<Integer, Integer> map = new TreeMap<>(); 
map.put(1, 10); 
map.put(0, -10); 
map.put(5, 25); 
map.put(3, 20); 

// find the value below. 
int key = 2; 
Map.Entry<Integer, Integer> entry1 = map.floorEntry(key); 
Map.Entry<Integer, Integer> entry2 = map.ceilingEntry(key); 
System.out.println(key + " is between " + entry1 + " and " + entry2);

打印

2 is between 1=10 and 3=20

插入，更新，查詢和刪除有O(log N)

一個時間複雜度

來源

2012-08-22 13:55:14

匹配值最接近值範圍內以最簡單的

回答

相關問題