面试挑战:在两个数组中找出不同的元素

Question

• 阶段1：给定两个数组，比如A[]和B[]，你怎么能发现B的元素是否在A中？

• 第二阶段：A[]的大小是10000000000000…而B[]比这个小得多？

• 第三阶段：B[]的大小也是10000000000。。。。。？

我的回答如下：

• 第1阶段：

  1. 双循环-O(N^2(
  2. 排序A[]，然后二进制搜索-O(NlgN(

• 第2阶段：使用位集，因为整数是32位。。。。

• 第三阶段：。。

你有什么好主意吗？

Answer 1

对A中的所有元素进行散列[迭代数组并将元素插入散列集中]，然后迭代B，并检查每个元素是否在B中。可以得到CCD_ 3的平均运行时间。

您无法获得亚线性复杂性，因此此解决方案对于平均情况分析是最佳的，但是，由于哈希是而不是O(1)最坏情况，因此您可能会获得较差的最坏情况性能。

编辑：

如果您没有足够的空间在B中存储元素的哈希集，您可能需要使用bloom过滤器来协调概率解决方案。问题是：可能会有一些假阳性[但绝对不会有假阴性]。当您为布隆过滤器分配更多空间时，正确性的准确性会增加。

另一个解决方案是，如您所说，排序，将是O(nlogn)时间，然后对排序数组上B中的所有元素使用二进制搜索。

对于第三阶段，您将获得相同的复杂性：O(nlogn)具有相同的解决方案，它将花费大约两倍于第二阶段的时间，但仍然是O(nlogn)

第2版：
请注意，有时您可以使用trie(取决于元素类型(来代替常规哈希，例如：对于int，将数字存储为字符串，每个数字都像一个字符。使用这个解决方案，您可以得到O(|B|*num_digits+|A|*num_digits)解决方案，其中num_digits是数字中的位数[如果它们是整数]。假设num_digits有界于有限大小，则得到O(|A|+|B|)最坏情况。

Answer 2

第1阶段：从A生成一个哈希集，并在B上迭代，检查当前元素B[i]是否存在于A中(与@amit之前提出的方法相同(。复杂度(平均值(-O(长度(A(+长度(B((。

第二阶段：从B生成一个散列集，然后在A上迭代，如果当前元素存在于B中，则将其从B中删除。如果迭代后的B至少有一个元素，则不是所有B的元素都存在于A中；否则CCD_ 23是CCD_。复杂度(平均值(-O(长度(A(+长度(B((。

第3阶段：对两个数组进行适当的排序并迭代，在当前位置i和j上搜索相同的数字以查找A[i]和B[j](这个想法必须显而易见(。复杂性-O(n*logn(，其中n=长度(A(。