匹配值最接近值范围内以最简单的

我遇到了，我需要一些帮助，一个问题 - 假设我有包括键（整数）和值（整数和）一些数据集。我需要能够给定一个键的一些值，发现最小范围的关键其所属（即，寻找最近的较大和较小的键），然后通过插值返回的匹配值。我想知道哪种方式可以让我在最快的时间内完成这个任务（空间复杂性问题要小得多）。同时，删除是无关紧要的，所有值都在启动时（我们可以假设会有启动后不再添加值）给出。我的重点是搜索时间，而不是插入。匹配值最接近值范围内以最简单的

最基本的解决方案将是，以保持键的排序后的数组，并在其上使用二进制搜索 - 直到我找到输入键或发现其比输入键较大和较小两个相邻元件。这个选项需要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

匹配值最接近值范围内以最简单的

回答

相关问题