我遇到了这篇文章,报道了以下的面试问题:
给定两个数字数组,找出两个数组中的每个数组是否具有相同的整数集？建议一个比NlogN跑得更快但没有额外空间的算法？
我能想到的最好的是以下几点:
(a)对每个数组进行排序,然后(b)沿两个数组移动两个指针并检查是否找到不同的值......但步骤(a)已经有NlogN复杂度:(
(a)扫描最短的数组并将值放入地图中,然后(b)扫描第二个数组并检查是否找到了一个不在地图中的值...这里我们有线性复杂度,但我们使用额外的空间
......所以,我想不出这个问题的解决方案.
想法？
谢谢你的所有答案.我觉得很多都是对的,但我决定选择ruslik的那个,因为它提供了一个我没有想到的有趣选项.
来源:微软访谈问题
我们得到一个包含单词的文件.我们需要确定其中存在的所有Anagrams.
有人可以建议最优化的算法来做到这一点.
我知道的唯一方法是 排序所有单词,然后检查.
我们能否通过获取字符串中每个字符的ascii值，然后找到所有字符的总和，然后为其他字符串计算出相同的字符，然后比较两个值（总和）来解决七巧板测试难题？
可行吗