algorithm - 确定有序数组复杂度之间的交集

Question

问题:给定两个大小为 n 的有序数组 A[] 和 B[]，检查它们是否有非空交集(我不需要交集本身，只需要决定)

解决方案:在 B[] 中对 A[] 的每个元素进行二进制排序给出 O(n lg n) 的解决方案。从头到尾迭代每个数组(执行与 Mergesort 中的 Merge 非常相似的操作)给出 O(n) 的解决方案。

我想知道是否有更好的(就复杂性而言)解决方案。我很确定没有，但我一直在寻找“嘿，如果你给我一个更好的解决方案，我可以在 o(n lg n) 中对向量进行排序，这是不可能的”-kind-of-argument

Answer 1

再次阅读问题 - "Given two <strong>sorted</strong> arrays ..." .

最初建议的排序是不需要的，它会引导您进入 O(n)执行类似合并排序过程的解决方案。

没有比类似合并排序的过程更好的了，请记住，如果发现交叉点，您可以提前停止。

如果它们没有排序:

基于 HashMap 的解决方案在技术上是 O(n) - 将 A 中的所有元素插入 HashMap (O(n))。查找 B ( O(n)) 中的每个元素。

对于排序解决方案，由于您只需要一个决定，因此您只需对 A 进行排序并循环遍历 B，执行 O(log n)在 A 中查找 B 中的每个元素，并在找到一个项目后停止。你不会比 O(n log n) 做得更好, 但如果及早找到匹配项，您可以减少一半的工作量。