algorithm - 面试挑战 : Find the different elements in two arrays

Question

• Stage 1: Given two arrays, say A[] and B[], how could you find out if elements of B is in A?

• Stage 2: What about the size of A[] is 10000000000000... and B[] is much smaller than this?

• Stage 3: What about the size of B[] is also 10000000000.....?

我的回答如下:

• 第 1 阶段:

  1. 双循环 - O(N^2);
  2. 排序 A[]，然后二分查找 - O(NlgN)

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

• 第 3 阶段:..

你有什么好的想法吗？

Answer 1

对 A 中的所有元素进行哈希处理 [迭代数组并将元素插入哈希集]，然后迭代 B，并检查每个元素是否在 B 中> 或不。您可以获得 O(|A|+|B|) 的平均运行时间。

您无法获得次线性的复杂度，因此此解决方案对于平均案例分析是最佳的，但是，由于散列不是 O(1) 最坏情况，你可能会得到糟糕的最坏情况性能。

编辑:

如果您没有足够的空间来存储 B 中的哈希元素集，您可能需要考虑使用 bloom filters 的概率解决方案.问题:可能存在一些误报 [但绝不会出现误报]。当您为布隆过滤器分配更多空间时，正确率会提高。

另一种方案就是如你所说，排序，这将是O(nlogn)时间，然后在排序后的数组上对B中的所有元素使用二分查找。

对于第 3 阶段，你得到相同的复杂度:O(nlogn) 使用相同的解决方案，大约需要比第 2 阶段多一倍的时间，但仍然是 O(nlogn)

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