问题：给定两个大小为 n 的排序数组 A[] 和 B[]，检查它们是否有非空交集（我不需要交集本身，只需要决定）
解决方案：在 B[] 中对 A[] 的每个元素进行二进制排序会得到 O(n lg n) 的解决方案。从头到尾迭代每个数组（做一些与 Mergesort 中的 Merge 非常相似的事情）给出 O(n) 解决方案。
我想知道是否有更好的（就复杂性而言）解决方案。我很确定没有，但我一直在寻找“嘿，如果你给我一个更好的解决方案，我可以在 o(n lg n) 中对向量进行排序，这是不可能的”--kind-of-argument
再次阅读问题 - 。"Given two sorted arrays ..."
不需要最初建议的排序，这会引导您找到O(n)执行类似合并排序过程的解决方案。
您不能比类似合并排序的过程做得更好，请记住，如果找到交叉点，您可以提前停止。
如果它们没有被排序：
从技术上讲，基于哈希映射的解决方案是O(n)- 将 A 中的所有元素插入哈希映射 ( O(n))。O(n)查找 B ( )中的每个元素。
对于排序解决方案，由于您只需要一个决策，因此您只需对 A 进行排序并遍历 B，O(log n)在 A 中对 B 中的每个元素进行查找，并在找到项目后停止。您不会做得比 更好O(n log n)，但如果尽早找到匹配项，您可以减少多达一半的工作。