从本质上讲，此问题减少为 联接 操作，然后为 过滤器 操作（删除重复项并仅保留内部匹配项）。

由于输入均已排序，因此可以通过合并连接（O（size（a）+
size（b）））有效地实现连接。

该 过滤器
操作将是O（N），因为删除的连接进行排序，并输出复制所有你需要做的是检查，如果每个元素都和以前一样它的人。仅过滤内部匹配项很简单，您只需丢弃所有不匹配的元素（外部联接）。

并行处理（在连接和过滤器中）都有机会获得更好的性能。例如，Hadoop上的Apache
Pig框架提供了合并联接的并行实现。

在性能和复杂性（以及可维护性）之间存在明显的权衡。因此，我想说，一个采访问题的好答案确实需要考虑绩效要求。

• 基于集合的比较-O（nlogn）-比较慢，非常简单，如果不存在性能问题，则使用。简单胜出。

• 合并连接+过滤器-O（n）-快速，容易出现编码错误，如果性能存在问题，请使用。理想情况下，尝试利用现有库来执行此操作，或者在适当的情况下甚至使用数据库。

• 并行实施-O（n / p）-非常快，需要其他基础设施，如果体积非常大且预计会增长，则使用该基础设施是主要的性能瓶颈。

（还请注意，问题 intersectSortedArrays
中的函数本质上是修改后的合并联接，该过程在联接期间进行过滤。此后，尽管内存占用量略有增加，也可以进行过滤而不会造成性能损失）。

最后的想法。

实际上，我怀疑大多数现代商业RDBMS在其连接的实现中都提供线程并行性，因此Hadoop版本提供的是机器级并行性（分布）。从设计的角度来看，对于这个问题，也许一个好的简单解决方案是将数据放在数据库中，在A和B上建立索引（有效地对数据进行排序）并使用SQL内部联接。