哪种数据结构对键值对是有效的？
哪种数据结构对键值对是有效的？
提问于 2017-06-21 05:15:47
Key value
1-5 A
7-10 B
11-15 C如果输入为4，输出A，输入为8，输出为B，依此类推。我可以使用哪种数据结构来存储以下数据，所以您不应该多次存储值。
我说的是HashMap，但它不是有效的。
P.S.我是在面试中被邀请的。
回答 3
Stack Overflow用户
回答已采纳
发布于 2017-06-21 05:34:32
使用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
nullStack Overflow用户
发布于 2017-06-21 05:25:01
我想面试官是在寻找ConcurrentNavigableMap的答案
可以用值保存几个键。
就你而言：
public static NavigableMap<Integer, String> map = new TreeMap<Integer, String>();
static {
map.put(1, "A"); // 1..5 => A
map.put(6, null); // 6 => empty
map.put(7, "B"); // 7..10 => N
map.put(11, "C"); // 11..15 => C
map.put(16, null); // 16.. => empty
}然后得到价值
map.floorEntry(4).getValue()Stack Overflow用户
发布于 2017-06-21 05:27:52
由于键不重复，可以使用数组索引作为键：
int[] array = {0,A,A,A,A,A,0,B,B,B,B,C,C,C,C,C,};现在在array[1] - array[5]有值A，在array[7] - array[10]值是B
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/44667322
复制相关文章
相似问题
腾讯云开发者
