nul*_*ull 1 algorithm performance hashmap prime-factoring
我最近有一个SE电话的电话,被问到我如何确定两个单词是否是字谜,我给出了一个回复,其中涉及获取字符的内容,迭代单词,如果它存在退出循环等等.我认为这是一个N ^ 2解决方案,每个单词有一个循环,内部循环用于比较.
电话结束后,我做了一些挖掘并写了一个新的解决方案; 我计划明天在下一阶段的访谈中使用一个哈希映射,它使用一个哈希映射,其中唯一的素数代表字母表中的每个字符.然后我循环遍历单词列表,计算单词的值并检查它是否与我正在检查的单词进行比较.如果值匹配,我们有一个赢家(整个数学定理业务).
这意味着一个循环而不是两个更好但我开始怀疑自己,并且想知道散列图和乘法的附加操作是否比原始建议更昂贵.
我99%肯定哈希地图会更快但是......
任何人都可以证实或否认我的怀疑吗？谢谢.
编辑:我忘了提到我在考虑做任何事情之前先检查单词的大小.
anagram包含原始单词的所有字母,顺序不同.你是在正确的轨道上使用a HashMap来处理线性时间的单词,但你的素数想法是一个不必要的复杂性.
您的数据结构可以HashMap维护各种字母的数量.您可以在O(n)时间内添加第一个单词的字母.关键是字符,值是频率.如果该字母不在HashMap尚未出现,put则其值为1.如果是,请更换它value + 1.
迭代第二个单词的字母时,从计数中减去一个,当它到达时删除一个字母0.如果您尝试删除不存在的字母,则可以立即声明它不是字谜.如果你到达终点并且HashMap不是空的,那它不是一个字谜.不然,这是一个字谜.
或者,您可以HashMap使用数组替换它.数组的索引对应于字符,值与以前相同.如果一个值下降-1,它不是一个字谜,如果任何值不是,那么它不是最后的字谜0.
你总是可以比较原始字符串的长度,如果它们不相同,那么它们就不可能是字谜.在开头包括此检查意味着您不必检查所有值是否0在最后.如果字符串长度相同,那么任何东西都会生成一个-1或者最后会有所有0s.
| 归档时间： |
|
| 查看次数： |
205 次 |
| 最近记录： |