使用java地图进行范围search
我有一个用例，如果一个数字在0-10之间，它应该返回0，如果它介于11-20之间，它应该返回1等
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地图，但它不允许范围search
我对这样的事情感兴趣，我有一个function
int foo() { }
如果foo返回5，因为它介于0到10之间，我会使用0，如果foo返回25，它将使用2。
有任何想法吗
编辑：实际上，范围并不像0-10,11-20那么简单。 我希望能够做范围search。 对于混淆抱歉。 根据查询，我添加了正确的例子，数字是连续的
对于范围不统一和存在“漏洞”的更普遍问题，我可以想到一些可能的解决scheme。 最简单的是：
- 只需为所有有效的键值填充一个映射，多个键映射到相同的值。 假设你使用HashMaps，这应该是最省时的（O（1）查找），尽pipe你在安装时有更多的工作，并且使用更多的空间。
- 使用NavigableMap并使用
floorEntry(key)进行查找。 这应该是更less的时间效率（O（日志（N）查找），但更多的空间效率。
这里有一个使用NavigableMaps的解决scheme，它允许映射中的“漏洞”。
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(); }
伪代码：
- 将范围边界存储在平面数组中：
new int[] {0, 3, 5, 15, 100, 300}。 - 像在数组中插入数字一样在数组中进行二进制search。 请参阅
Arrays.binarySearch()。 - 如果插入点是偶数，则该数字不适合任何范围。
- 如果插入点是奇数，则它适合相应的范围。 例如，上述数组中的
10的插入点为3，将其置于5和15之间，因此它属于第二个范围。
在不能用算术解决的更一般的情况下，可以用适当的比较器创build一个TreeMap。 为边界值添加映射，然后使用ceilingEntry或floorEntry来查找适当的匹配。
我想你想要的是沿着foo()/10 ，但是这会使你的范围稍微偏离你的要求。 如果他们不遵循一个简单的模式，你总是可以对“地图”中每个项目的两个端点进行比较。
我认为最简单的解决scheme是将范围上限的映射添加到范围映射的值，然后继续增加数字（键在映射中），直到达到映射（这是映射的上限）你的号码范围在）。
另一种方法是用一个范围内的所有条目填充地图，并为每个条目添加一个映射。
哪一个更有效率取决于是否可能需要重复请求一个范围内的所有数字（使用后者的解决scheme），还是仅仅使用一些数字（使用第一个）
