我测试了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).