我测试了codesignal,但没能解决这个问题。
创建允许以下操作的数据结构。
插入x y-插入具有键x和值y的对象。
get x-返回键为x的对象的值。
addtokey x-将x添加到Map中的所有关键点
addtovalue y-将y添加到Map中的所有值。
每个操作的时间复杂度应为o(log(n))
我能够用java中的array和linkedlist制作一个散列图。但我无法将时间复杂度设为o(log(n))。在我的实现中,insert和get的时间复杂度是o(1)(在最坏的情况下是o(n))。addtokey和addtovalue的时间复杂度是o(n),因为我必须迭代所有元素来修改键和值。
对于这个问题,什么是合适的数据结构?
1条答案
按热度按时间f45qwnt81#
经过编辑,在vee和tom elias的有益评论后更正了答案。
你不能实现
addToKey
以及addToValue
通过迭代所有元素,因为这需要线性时间。相反,你可以保持
keyDelta
以及valueDelta
int
示例变量,其中包含应分别添加到每个键和值的值(或所有值的总和)。这是假设addToKey
以及addToValue
应该为键或值添加一个数值。addToKey
以及addToValue
只需要更新那些示例变量O(1)
.这个
get(x)
操作将搜索密钥x - keyDelta
相加后返回相应的值valueDelta
去吧。请注意
add(x,y)
还需要进行更改,因为添加到Map的键值对不应受到以前对的调用的影响addToKey
或者addToValue
. 如果insert(x,y)
将实际插入一对x - keyDelta, y - valueDelta
到Map上去。如果你使用
TreeMap
要实现键到值的Map,get
以及insert
可能需要O(logN)
.