使用 Java 映射进行范围搜索

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

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

  1. 只需填充所有有效键值的 Map,将多个键映射到同一值即可。假设您使用HashMaps,这应该是最省时的(O(1)查找),尽管您在设置时有更多的工作并且使用更多的空间。
  2. 使用导航地图并用于执行查找。这应该更省时(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

伪代码:

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

推荐