我在CodeSignal上进行了测试,但无法解决这个问题。
创建允许以下操作的数据结构。
insert xy - 插入一个带有键 x 和值 y 的对象。
get x - 返回带有键 x 的对象的值。
addToKey x - 将 x 添加到映射中的所有键
addToValue y - 将 y 添加到映射中的所有值。
每个操作的时间复杂度应该是O(log(N))
我能够使用 Java 中的数组和 LinkedList 制作哈希图。但我无法将时间复杂度提高到 O(log(N))。在我的实现中,插入和获取的时间复杂度为 O(1)(最坏情况下为 O(N))。addToKey 和 addToValue 的时间复杂度是 O(N),因为我必须迭代所有元素来修改键和值。
对于这个问题来说,合适的数据结构是什么?