我遇到了这篇文章,报道了以下的面试问题:
给定两个数字数组,找出两个数组中的每个数组是否具有相同的整数集？建议一个比NlogN跑得更快但没有额外空间的算法？
我能想到的最好的是以下几点:
(a)对每个数组进行排序,然后(b)沿两个数组移动两个指针并检查是否找到不同的值......但步骤(a)已经有NlogN复杂度:(
(a)扫描最短的数组并将值放入地图中,然后(b)扫描第二个数组并检查是否找到了一个不在地图中的值...这里我们有线性复杂度,但我们使用额外的空间
......所以,我想不出这个问题的解决方案.
想法？
谢谢你的所有答案.我觉得很多都是对的,但我决定选择ruslik的那个,因为它提供了一个我没有想到的有趣选项.
在我的环境中，Gperf 的性能始终低于 Judy 数组，我想知道是否有另一个专门为整数键构建的完美哈希库。我事先知道一组键，并且我想利用它来获得性能/尺寸优势。
有大约 1000 个键，并且检索不按顺序排列。密钥对都是整数。密钥是 32 位，检索的值是 8 位。尺寸是最重要的因素。
如果有一种方法可以针对整数键调整 Gperf，或者只是另一种方法，我也会洗耳恭听。:)
（旁注：...在输入这个问题时，我意识到二分搜索可能会更有效，而且我只是过度思考了这个问题。为了学习，我仍然想听听您的任何想法，尽管！）
编辑：键分布不均匀。大多数是在整个可能的范围内随机聚集的。
编辑 2：最坏情况的二进制搜索对我来说太慢了，所以我最终使用了这些键，直到我找到每个键可以使用 8 位来创建 256 个均匀分布的存储桶。我保存了每个桶的最小值和最大值（每个桶条目 24 位），并为密钥对创建了一个大的结构数组。与我在特定情况下测试的其他所有产品相比/更快且更小，所以我想我现在就采用它。:)
可能重复:
检查数组B是否为A的排列
给出2个未排序的整数数组a并且b大小相等.确定是否b是一个排列a.可以这样在做O(n) time和O(1) space？
我想到的第一个解决方案就是使用XOR,即XOR all the elements of a and b and if the resultant is 0 which means that b is a permutation of a.但他给出了这种方法失败的例子.例如 -
a: [1 6 0 0 4] -- b: [1 0 6 1 5]
a: [1 6 0 0 5] -- b: [1 0 6 1 4]
任何一个有任何想法,如何做到O(n) time和O(1) space？