为了账号安全,请及时绑定邮箱和手机立即绑定

面试题,一个key-value容器的实现问题?

面试题,一个key-value容器的实现问题?

Smart猫小萌 2018-08-01 17:29:18

今天在网上看到了一道别人分享的数据结构面试题,要求实现一个key-value容器,支持如下操作:
1.根据key获取元素
2.根据key删除元素
3.插入元素
4.根据value获取key
以上操作时间复杂度均要求在O(log N)以内。
用平衡树可以实现前三条,有没有哪种数据结构可以一并实现第四条的?

查看完整描述

3 回答

?
qq_花开花谢_0

TA贡献1477条经验 获得超5个赞

前三个都很好做,但是第四个问题描述得不够清楚,因为可能多个key对应的都是相同的value,所以根据value去获取key就比较麻烦了,结果可能是一个数组。如果保证一一对应,key和value也都是唯一的,那么像楼上说的简单的两棵平衡树就可以解决


查看完整回答
反对 回复 2018-08-05
?
万千封印

TA贡献1541条经验 获得超3个赞

一下能想到的是个很二的办法:用两棵树……
没特殊约束的话,说不定我真的会这么实现。

查看完整回答
反对 回复 2018-08-05

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信