金男人OA

AlbertZhong 发表于 2020-07-09 19:16:27
用rolling hash的方法，尽管几率不高，但是遇到hash值完全相同时还是有可能出现冲突的情况（多个不同的字符串有同一个hash值），感觉还是免不了一个个从头到尾去检查一遍。。。

。。。。。你每个点左右展开不就是O(N^2)嘛

AlbertZhong 发表于 2020-7-10 10:16
用rolling hash的方法，尽管几率不高，但是遇到hash值完全相同时还是有可能出现冲突的情况（多个不同的字 ...

hash collision的几率其实很高，解决方法一般是双hash

闵医事豆吉拉 发表于 2020-07-09 19:24:08
。。。。。你每个点左右展开不就是O(N^2)嘛

所以你的意思是 枚举中点？

补充内容 (2020-7-9 19:49):
再配合hashmap 去重？

您好！
本帖隐藏的内容需要积分高于 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

lbytenwater 发表于 2020-07-10 08:21:45
不太懂，为啥要自己写hash， 直接用hashSet不香么？

你没懂我意思，你想想你hash一个string的时候under the hood发生了什么就知道了。

闵医事豆吉拉 发表于 2020-07-10 09:34:35
你没懂我意思，你想想你hash一个string的时候under the hood发生了什么就知道了。

我懂呀，严格意义上来说，hashSet 不是O1，但是你自己写也不是O1呀，既然都一样，为什么不用语言里自带的？