44

我有一个用例，如果一个数字在 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 那样简单。我希望能够进行范围搜索。很抱歉造成混乱。根据我添加了正确示例的查询，数字是连续的

4

6 回答 6

93

对于范围不统一且存在“漏洞”的更普遍的问题，我可以想到许多可能的解决方案。最简单的是：

  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();
}
于 2009-08-21T23:58:36.573 回答
12

伪代码：

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

在无法用算术解决的更一般情况下，您可以使用适当的比较器创建 TreeMap。为边界值添加映射，然后使用 ceilingEntry 或 floorEntry 找到合适的匹配。

于 2009-08-21T23:52:26.647 回答
0

我认为您想要的是类似于 的东西foo()/10，但这会使您的范围与您的要求略有不同。如果它们不遵循简单的模式，您总是可以对“地图”中每个项目的两个端点进行比较。

于 2009-08-21T23:41:37.747 回答
0

我认为最简单的解决方案是将范围上边界的映射添加到范围映射到的值，然后不断增加数字（地图中的键）直到到达映射（这是您的号码所在的范围）。

另一种方法是用一个范围内的所有条目填充映射，并为每个条目添加一个映射。

哪个更有效取决于您是否可能需要重复请求一个范围内的所有数字（使用后一种解决方案），或者只是一些数字几次（使用第一个）

于 2009-08-22T00:45:17.867 回答
0

根据John Kugelman 的回答，我需要类似的东西来进行日期范围搜索，该搜索具有与日期范围相关的数据......这是我如何应用它的示例。“日期”将是您的键，“范围数据”将是关联的数据。

  long[] dates = new long[] {
    Instant.parse("1900-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1950-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1960-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1970-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1980-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1990-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("2000-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("2010-01-01T00:00:00Z").toEpochMilli()
  };
  String[] rangeData = new String[] {
    "Before 1900 data", "Before 1950 data", "Before 1960 data", 
    "Before 1970 data", "Before 1980 data", "Before 1990 data", 
    "Before 2000 data", "Before 2010 data"
  };
  
  long searchDate = Instant.parse("1949-02-15T00:00:00Z").toEpochMilli();
  int result = Arrays.binarySearch(dates, searchDate);
  
  System.out.println("Result: " + result); 
  if (result == dates.length) {
      System.out.println("Date is after all ranges");
      System.out.println("Data: none");
  }
  else if (result >= 0) {
      System.out.println("Date is an exact match of " + Instant.ofEpochMilli(dates[result]));
      System.out.println("Data: " + rangeData[result]);
  }
  else {
      int resultIndex = Math.abs(result) - 1;
      System.out.println("Date is before idx: "+ resultIndex + " date " + Instant.ofEpochMilli(dates[resultIndex]));
      System.out.println("Data: " + rangeData[resultIndex]);
  }

结果

Result: -2
Date is before idx: 1 date 1950-01-01T00:00:00Z
Data: Before 1950 data
于 2021-01-02T09:02:07.660 回答