G家电面

refurbish

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

感觉稀里糊涂的，问了一个现在工作的问题，就接着问了一个coding的题目：
实现一个Map，带有getRandomValue的方法，要求所

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

(2015-3-4 15:10):
刚收到消息，pass了

refurbish

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

refurbish

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

独孤辰涛

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

tonywen2014

楼主请问，getRandomValue 是取Value set里面的任意一个值？

refurbish

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

fsc111

refurbish 发表于 2015-3-4 03:09
对的，比如：
(1, "a")
(2, "b")

楼主请问你后来想出来O(1)的解法了吗，能提示下吗？

dsq704136

可以直接用HashMap实现Get, Put, Remove。用一个额外的Array去实现getRandom。

fsc111

refurbish 发表于 2015-3-7 17:13
楼上的回复是很好的提示，我的做法略有不同，因为我当时想着要不受固定大小的限制，我多用了两个hash tab ...

果然index不连续的话，怎么实现随机呢？

timtam85

refurbish

fsc111 发表于 2015-3-9 03:33
果然index不连续的话，怎么实现随机呢？

删除的时候，把对应的整数索引和最大的索引所映射的key对换，然后最大的整数索引减一保存

smallsimple

refurbish 发表于 2015-3-9 12:37
删除的时候，把对应的整数索引和最大的索引所映射的key对换，然后最大的整数索引减一保存

请教楼主，对换key之前要先找到要删除的key的索引，这个找的过程是O(n)吧？不知道是怎么实现的？我假设楼用了array保存key？