使用 Java 映射进行范围搜索

java maps

2022-08-31 23:49:39

我有一个用例，如果一个数字位于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地图，但它不允许范围搜索

我对这样的东西感兴趣，我有一个函数

int foo() {

}

如果 foo 返回 5 ，因为它位于 0 到 10 之间，我将使用 0，如果 foo 返回 25，它将使用 2。

任何想法

编辑：实际上范围并不像0-10，11-20那么简单。我希望能够进行范围搜索。很抱歉造成混淆。根据查询，我添加了正确的示例，数字是连续的

答案 1

我可以为范围不均匀且存在“孔”的更普遍的问题想出许多可能的解决方案。最简单的是：

只需填充所有有效键值的 Map，将多个键映射到同一值即可。假设您使用HashMaps，这应该是最省时的（O（1）查找），尽管您在设置时有更多的工作并且使用更多的空间。
使用导航地图并用于执行查找。这应该更省时（O（log（N）查找），但更节省空间。floorEntry(key)

这是一个使用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();
}

答案 2

伪代码：

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