用java地图范围搜索

我有一个使用情况下，如果一些位于0-10之间，它应该返回0，如果它位于11-20之间，它应该返回1等用java地图范围搜索

0 => 0-3, (0 and 3 are inclusive) 
1 => 4-15, (4 and 15 are inclusive) 
2 => 16-40, (16 and 40 are inclusive) 
3 => 41-88, (41 and 88 are inclusive) 
5 => 89-300 (89 and 300 are inclusive)

我在想我怎么可能实现并打算java的地图，但它不允许范围的搜索，

我感兴趣的是这样的，我有一个函数

int foo() { 

}

检查foo返回5，因为它介于0 Ť O 10我会用0，如果富回报25，将利用2

任何想法

编辑：其实范围并不如0-10，11-20那样简单。我想能够做范围搜索。对此感到抱歉。根据查询，我添加了正确的例子，数字是连续的

来源

2009-08-21 kal

请提供一个你想做什么的真实例子。 – 2009-08-22 00:19:16

示例中给出的范围不是连续的。如果搜索4或50，是否需要'null'结果，上面，下面或最近的范围，或者什么？ – erickson 2009-08-22 00:20:36

@mkal：你继续改变需求的方式，你可能是地狱经理:-) – 2009-08-22 01:00:25

对于范围不均匀且存在“漏洞”的更一般性问题，我可以想到一些可能的解决方案。最简单的是：

只需为所有有效键值填充一个映射，并将多个键映射到相同的值。假设你使用HashMaps，这应该是最省时间的（O（1）查找），尽管你在安装时有更多的工作，并且使用更多的空间。
使用NavigableMap并使用floorEntry(key)进行查找。这应该是更短的时间高效（O（日志（N）查找），但更多的空间效率更高。

下面是使用NavigableMaps一个解决方案，允许在映射“洞”。

private static class Range { 
    public int upper, value; 
    ... 
} 

NavigableMap<Integer, Range> map = new TreeMap<Integer, Range>(); 
map.put(0, new Range(3, 0));  // 0..3  => 0 
map.put(5, new Range(10, 1));  // 5..10 => 1 
map.put(100, new Range(200, 2)); // 100..200 => 2 

// To do a lookup for some value in 'key' 
Map.Entry<Integer,Range> entry = map.floorEntry(key); 
if (entry == null) { 
    // too small 
} else if (key <= entry.getValue().upper) { 
    return entry.getValue().value; 
} else { 
    // too large or in a hole 
}

在另一方面，如果不存在 '洞' 的解决方案是简单的：

NavigableMap<Integer, Integer> map = new TreeMap<Integer, Integer>(); 
map.put(0, 0); // 0..4  => 0 
map.put(5, 1); // 5..10 => 1 
map.put(11, 2); // 11..200 => 2 

// To do a lookup for some value in 'key' 
if (key < 0 || key > 200) { 
    // out of range 
} else { 
    return map.floorEntry(key).getValue(); 
}

来源

2009-08-21 23:58:36

这是非常好的使用现有的TreeMap做一个简单的范围搜索。请注意，如果存在重叠间隔，则该方法将返回该间隔，并使用与查找键最接近的较低键。同样，此方法不支持搜索包含给定搜索关键字的所有重叠区间，如http://stackoverflow.com/questions/1580185/data-structure-for-quick-time-interval-look-up – stackoverflowuser2010 2011-11-07 18:45:11

中所述如果有重叠的范围，则范围（很可能）不正确地指定。至少，这是我对这个问题的阅读。 – 2013-03-21 05:16:10

我认为你想要的是沿着foo()/10行的东西，但这会给你略微偏离你请求的范围。如果他们不遵循一个简单的模式，您可以随时对“地图”中每个项目的两个端点进行比较。

来源

2009-08-21 23:41:37

在无法用算术解决的更一般情况下，可以使用适当的比较器创建TreeMap。为边界值添加映射，然后使用ceilingEntry或floorEntry查找适当的匹配。

来源

2009-08-21 23:52:26 Ken

伪代码：

将范围边界存储在平面数组中：new int[] {0, 3, 5, 15, 100, 300}。
像在数组中插入数字一样对数组进行二进制搜索。请参阅Arrays.binarySearch()。
如果插入点是偶数，则该数字不适合任何范围。
如果插入点是奇数，则它适合相应的范围。例如，上述阵列中10的插入点将为3，因此它位于5和15之间，因此它属于第二个范围。

来源

2009-08-22 00:04:19

注意：这只适用于映射到整数“{0，1，2，...}”的情况。对于更一般的情况，应该使用某种类型的地图。 – 2009-08-22 00:27:46

我认为最简单的解决方案是将范围上限的映射添加到范围映射到的值，并且只是继续递增您的数字（键在映射中），直到您到达映射（其中是您的号码所在范围的上限）。

另一种方法是用范围内的所有条目填充地图，并为每个条目添加一个映射。

哪一个更有效取决于它是否有可能需要请求所有指数值范围内反复（使用后者的解决方案），或者只是一些数字的几十倍（使用第一）

来源

2009-08-22 00:45:17 Jorn

用java地图范围搜索

回答

相关问题