如何有效地在整数范围列表中搜索 - java

Question

如何有效地在整数范围列表中搜索？

我有一些具有重复值的范围列表。如果输入数字在范围内，我想得到 value。

例如

Range Start	Range End	Value
10	75	A
95	200	A
300	455	B
570	650	C
201	250	A
255	275	B

注意：开始和结束范围不重叠。

输入 260 预期输出 B
输入 195 预期输出 A

目前，我在 HashMap 中保存并存储 {“10-75” , A} {’95-200”, B}... 我是

遍历Map的所有键，
拆分每个键，
转换为 int 并
检查给定的数字是否在范围内。
如果是，获取该键的值

我想 Java 中可能有一些更有效的方法来处理这个问题。

如有任何帮助，我们将不胜感激。

Answer 1

您可以使用 Guava 的 RangeMap:

RangeMap<Integer, Character> rangeMap = TreeRangeMap.create();
rangeMap.put(Range.closed(10, 75), 'A');
rangeMap.put(Range.closed(95, 200), 'A');
rangeMap.put(Range.closed(300, 455), 'B');
rangeMap.put(Range.closed(570, 650), 'C');
rangeMap.put(Range.closed(201, 250), 'A');
rangeMap.put(Range.closed(255, 275), 'B');

Character character = rangeMap.get(61);
Character character2 = rangeMap.get(244);
Character character3 = rangeMap.get(270);

System.out.println(character);
System.out.println(character2);
System.out.println(character3);

输出：

A
A
B

注意：出于某种原因，它标有 @Beta https://github.com/google/guava/issues/3376 所以我想确保它是否适合生产使用。

Answer 2

你为什么不尝试三个 if-else 语句？

假设：范围的起始值和结束值被视为给定范围内的值。

'D'表示给定的值不属于定义的范围值。

示例代码：

 public static char findRangeValue(int number){

        if((number >= 10 && number <=75) ||(number >= 95 && number <=250) ){
            return 'A';
        }else if((number >= 255 && number <=275) ||(number >= 300 && number <=455)  ){
            return 'B';
        }else if(number >= 570 && number <=650 ){
            return 'C';
        }
           return 'D';
    }

示例方法调用和输出：

  public static void main(String[] args) {

        System.out.println(findRangeValue(265));
        System.out.println(findRangeValue(11));
        System.out.println(findRangeValue(575));
    }

输出：

B
A
C

Answer 3

您可以使用 TreeMap 和 Entry 像这样使用常规 Java 来完成。如果提供的参数不存在范围，则它 returns Not Found

这是包含范围的地图。

它是一个 TreeMap
键是范围的下半部分。
值是一个 AbstractMap.SimpleEntry，包含范围的上半部分和字符串。

NavigableMap<Integer, AbstractMap.SimpleEntry<Integer,String>> nmap =
        new TreeMap<>();

地图的构建方法。

public static void build(
        NavigableMap<Integer, AbstractMap.SimpleEntry<Integer, String>> map,
                                         int start, int end, String v) {
        AbstractMap.SimpleEntry<Integer, String> e = new 
                    AbstractMap.SimpleEntry<Integer,String>(end,v);
        map.put(start, e);
}

用于检索字符串的 lambda。

Function<Integer,String> get = k->{
        Entry<Integer, AbstractMap.SimpleEntry<Integer,String>> entry = 
                             nmap.floorEntry(k);
        if (entry == null) {
                  return "Not Found";
        }
        if (k > entry.getValue().getKey()) {
                  return "Not Found";
        }
        return entry.getValue().getValue();        
};

为每个范围构建地图

build(nmap, 10, 75, "A");
build(nmap, 95, 200, "A");
build(nmap, 300, 455, "B");
build(nmap, 570, 650, "C");
build(nmap, 201, 250, "A");
build(nmap, 255, 275, "B");

测试

int[] testData = { 9, 23, 255, 99, 94, 201 };
for (int i : testData) {
    System.out.printf("%4d -> %s%n",i, get.apply(i));
}

版画

   9 -> Not Found
  23 -> A
 255 -> B
  99 -> A
  94 -> Not Found
 201 -> A

如何有效地在整数范围列表中搜索 - java

How to search within list of integer ranges efficiently - java

java

list

hashmap

range