gpt4 book ai didi

algorithm - 我可以使用什么结构将唯一键映射到唯一值?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:29:48 29 4
gpt4 key购买 nike

Map可以解决key唯一时O(1)的搜索方案。

但是是否存在一种结构,其中按键搜索和值搜索都采用 O(1) 顺序?

给定一个结构:

Put(key,value)
GetValueOf(Key) in O(1)
GetKeyOf(Value) in O(1)

有没有一种方法可以在不使用 2 个 map 的情况下按顺序完成两次搜索?

我对 java 实现特别感兴趣。

提前致谢!!

最佳答案

您注意到当键唯一时,映射可以解决 O(1) 搜索解决方案。当两个键都是唯一的时,您需要一个 O(1) 搜索解决方案来搜索任何值。那么,这个数据结构就足够了:

class YourDoubleHashMap<K,V>() {
private HashMap<K,V> keyMap;
private HashMap<V,K> valMap;

YourDoubleHashMap<K,V>() {
keyMap = new HashMap<K,V>();
valMap = new HashMap<V,K>();
}
public boolean put(K key,V val) {
return keyMap.put(key,val) && valMap.put(val,key);
}
public V getValueOfKey(K key) {
return keyMap.get(key);
}
public K getKeyOfValue(V val) {
return valMap.get(val);
}
}

这种时间-内存权衡方法以牺牲空间效率来换取运行时效率。

关于algorithm - 我可以使用什么结构将唯一键映射到唯一值?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15159916/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com