查找两个数组是否包含相同的整数集,没有额外的空间且比NlogN更快

Question

我遇到了这篇文章,报道了以下的面试问题:

给定两个数字数组,找出两个数组中的每个数组是否具有相同的整数集？建议一个比NlogN跑得更快但没有额外空间的算法？

我能想到的最好的是以下几点:

1. (a)对每个数组进行排序,然后(b)沿两个数组移动两个指针并检查是否找到不同的值......但步骤(a)已经有NlogN复杂度:(

2. (a)扫描最短的数组并将值放入地图中,然后(b)扫描第二个数组并检查是否找到了一个不在地图中的值...这里我们有线性复杂度,但我们使用额外的空间

......所以,我想不出这个问题的解决方案.

想法？

---

谢谢你的所有答案.我觉得很多都是对的,但我决定选择ruslik的那个,因为它提供了一个我没有想到的有趣选项.

Answer 1

您可以通过选择用于累积的交换函数(例如,加法或XOR)和参数化散列函数来尝试概率方法.

unsigned addition(unsigned a, unsigned b);
unsigned hash(int n, int h_type);

unsigned hash_set(int* a, int num, int h_type){
    unsigned rez = 0;
    for (int i = 0; i < num; i++)
        rez = addition(rez, hash(a[i], h_type));
    return rez;
};

以这种方式,在您确定误报概率低于某个阈值之前的尝试次数将不依赖于元素的数量,因此它将是线性的.

编辑:在一般情况下,集合相同的概率非常小,因此使用多个散列函数进行的O(n)检查可用于预过滤:如果它们确实不同或者是否存在概率,则尽可能快地进行判断它们是等价的,如果应该使用缓慢的确定性方法.最终的平均复杂度将是O(n),但最坏的情况将具有清除方法的复杂性.

Answer 2

你在问题中说"没有额外的空间",但我认为你实际上是指"带有O(1)额外空间".

假设数组中的所有整数都小于k.然后你可以使用就地基数排序在时间O(n  log  k)中用O(log k)额外空间(对于堆栈,如注释中的yi_H所指出的)对每个数组进行排序,并比较排序后的数组O(n  log  k).如果k不随n变化,那么你就完成了.