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

Question

• 阶段1:给定两个数组,比如A []和B [],你怎么能知道B的元素是否在A中？

• 阶段2:A []的大小是10000000000000 ......而B []比这小得多？

• 阶段3:B []的大小也是10000000000 .....？

我的答案如下:

• 阶段1:

  1. for for loop - O(N ^ 2);
  2. 排序A [],然后二进制搜索 - O(NlgN)

• 阶段2:使用位集,因为整数是32位....

• 第3阶段:..

你有什么好主意吗？

Answer 1

哈希A[迭代数组并将元素插入哈希集]中的所有元素,然后迭代B,并检查每个元素是否B存在.你可以获得平均运行时间O(|A|+|B|).

您不能获得亚线性复杂性,因此该解决方案对于平均情况分析是最佳的,但是,由于散列不是 O(1) 最坏的情况,您可能会遇到糟糕的最坏情况性能.

编辑:

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

另一种解决方案就像你说的那样,排序,这将是O(nlogn)时间,然后对排序数组中B中的所有元素使用二进制搜索.

对于第3阶段,您会得到相同的复杂性:O(nlogn)使用相同的解决方案,它将花费大约两倍于第2阶段,但仍然如此O(nlogn)

EDIT2:
请注意,有时您可以使用trie [对元素类型进行depands] 而不是使用常规哈希,例如:对于int,将数字存储为字符串,每个数字都像一个字符.使用此解决方案,您可以获得O(|B|*num_digits+|A|*num_digits)解决方案,num_digits数字中的位数[如果它们是整数].假设num_digits有限大小,你会得到O(|A|+|B|) 最坏的情况.