使用java map进行范围搜索 [英] Using java map for range searches

问题描述

我有一个用例，如果一个数字介于0-10之间它应该返回0，如果它介于11-20之间它应该返回1等

I have a use case where if a number lies between 0-10 it should return 0 and if it lies between 11-20 it should return 1 etc

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地图，但它不允许范围搜索

I was thinking how could I implement and was thinking java maps, but it does not allow range searching

我对此类感兴趣，我有一个功能

I am interested in something like this , I have a function

int foo() {

}

如果foo返回5，因为它介于0到10之间，我会使用0，如果foo返回25则会使用2.

if foo returns 5 , since it lies between 0 to 10 I would use 0, if foo return 25 it would use 2.

任何想法

编辑：实际上范围并不像0-10,11-20那么简单。我希望能够进行范围搜索。对此感到抱歉。基于我添加了正确示例的查询，数字是连续的

Edit : Actually the ranges are not as simple as 0-10, 11-20. I want to be able to do range searches. Sorry about the confusion. Based on the queries I have added the correct example, the numbers are continous

推荐答案

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

I can think of a number of possible solutions for the more general problem where the ranges are not uniform and there are 'holes'. The simplest are:

1. 只需为所有有效键值填充Map，并将多个键映射到相同的值。假设您使用HashMaps，这应该是最有效的时间（O（1）查找），尽管您在设置时有更多工作并且您使用更多空间。


2. 使用NavigableMap和使用 floorEntry（key）进行查找。这应该是更少的时间效率（O（log（N）查找），但更节省空间。

1. Simply populate a Map for all valid key values, with multiple keys mapping to the same value. Assuming that you use HashMaps, this should be the most time efficient (O(1) lookups), though you have more work at setup time and you use more space.
2. Use a NavigableMap and use floorEntry(key) to do the lookups. This should be less time efficient (O(log(N) lookups) but more space efficient.

这是一个使用NavigableMaps的解决方案，允许对于映射中的洞。

Here's a solution using NavigableMaps that allows for 'holes' in the mapping.

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
}

另一方面，如果没有漏洞，解决方案就更简单了：

On the other hand, if there are no 'holes' the solution is simpler:

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();
}

这篇关于使用java map进行范围搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！