狗家店面4.10

xietianyi 发表于 2018-4-11 04:02
我觉得就算是hash算法，怎么着也得把每个字符串都扫一遍吧，m*n还能再低下去？压缩空间倒是有可能

我觉得也是。。可能面试官就随口说了一句。。感觉时间复杂度应该不能更小了

同意楼上，如果用list存index，刚才又查了一下，就算使用binary search来做查找和删除，时间复杂度依然是nlogn，因为list的add和remove操作其实是O(n)的，而pq的offer poll remove都是logn，有保障

wangchuqiao93 发表于 2018-4-12 03:11
那如果某个number的index被其他number覆盖了，就比较难操作了吧

就是说还是要两个hashmap，来处理replace的情况，但是我比较同意那个value放index的map用pq

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

xietianyi 发表于 2018-4-12 04:25
同意楼上，如果用list存index，刚才又查了一下，就算使用binary search来做查找和删除，时间复杂度依然是nl ...

没考虑到list的add操作需要O(n)的时间复杂度。。查了下是O(n)的时间复杂度

xietianyi 发表于 2018-4-12 04:27
就是说还是要两个hashmap，来处理replace的情况，但是我比较同意那个value放index的map用pq

是的 忘记了还有replace操作 还是需要两个map