哪种数据结构对键值对有效？

Question

Key           value
1-5           A
7-10          B
11-15         C

如果输入为4,则输出A,输入为8,输出为B,依此类推.我可以使用哪种数据结构来存储以下数据,因此您不应多次存储值.

我说HashMap,但效率不高.

PS我在面试时被问过.

Answer 1

使用TreeMap的值存储与键为间隔的结束点.然后检索的数据floorKey()和ceilingKey()任何关键的,如果这两个值相同则返回它否则返回null.这里的每个查询都需要O(log n)时间来回答,但与其他方法相比,空间复杂度非常低.在这里,我认为每个值都是唯一的interval,每个键只有一个与之关联的值.

TreeMap<Integer,String> map = new TreeMap<Integer,String>();

map.put(1,"A"); map.put(5,"A");
map.put(7,"B"); map.put(10,"B");
map.put(11,"C"); map.put(15,"C");

System.out.println(getData(4));
System.out.println(getData(6));

static String getData(int key)
{
    Integer ceiling_key= map.ceilingKey(key);
    Integer floor_key = map.floorKey(key);

    if(ceiling_key == null || floor_key == null)
        return null;

    String value1 = map.get(ceiling_key);
    String value2 = map.get(floor_key);

    if(value1.equals(value2))
        return value1;
    else
        return null;

}

输出:

A
null