使用java map进行范围搜索

Question

我有一个用例,如果一个数字位于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那么简单.我希望能够进行范围搜索.对此感到抱歉.根据我添加了正确示例的查询,数字是连续的

Answer 1

对于范围不均匀且存在"漏洞"的更普遍的问题,我可以想到一些可能的解决方案.最简单的是:

1. 只需为所有有效键值填充Map,并将多个键映射到相同的值.假设您使用HashMaps,这应该是最有效的时间(O(1)查找),尽管您在设置时有更多工作并且您使用更多空间.
2. 使用NavigableMap并用于floorEntry(key)执行查找.这应该是更少的时间效率(O(log(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();
}

Answer 2

伪代码:

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