输入：两个排序整数数组A和B分别以递增顺序和不同大小N和M分配
输出：一个排序整数数组C,按照递增的顺序包含出现在A和B中的元素
限制：C中不允许重复
示例：对于输入A = {3,6,8,9}和B = {4,5,9,10,11},输出应为C = {6,9}
谢谢你的答案,所有！总而言之,这个问题有两种主要方法：
我的原始解决方案是保留两个指针,每个数组一个,并从左到右互换扫描数组,同时选择匹配的元素.所以当我们当前的一个数组的元素大于第二个数组时,我们不断增加第二个数组的指针,直到找到当前的第一个数组元素或者超立方(找到一个).我保持所有匹配在一个单独的数组,一旦我们到达任一个输入数组的结尾,它返回.
我们可以这样做的另一种方法是线性扫描阵列之一,同时使用二进制搜索来在第二个数组中找到一个匹配项.这将意味着O(N * log(M))时间,如果我们扫描A和其每个N个元素在B(O(log(M))时间上的二进制搜索).
我已经实施了两种方法,并进行了一个实验,看看这两个比较(详细信息可以在here找到).当N具有100万个元素时,当M大约是N的70倍时,二进制搜索方法似乎胜出.
解决方法
由于输入都已经排序,所以可以通过O(O(size(a)size(b))的merge join来有效地实现连接.
过滤器操作将为O(n),因为连接的输出被排序,并且要删除重复项,所有您需要做的是检查每个元素是否与之前的元素相同.仅过滤内部匹配是微不足道的,您只是丢弃任何不匹配的元素(外连接).
并行机制(在连接和过滤器中)都有机会实现更好的性能.例如,Hadoop上的Apache Pig框架提供了parallel implementation的合并连接.
在性能和复杂性之间存在明显的权衡(从而可维护性).所以我会说一个很好的答案面试问题真的需要考虑到性能要求.
>设置比较 – O(nlogn) – 如果没有性能问题,相对较慢,非常简单.简单胜利.
>合并连接过滤器 – O(n) – 快速,容易出现编码错误,使用if
表现是一个问题.理想情况下,尝试利用现有库来执行此操作,或者甚至在适当的情况下使用数据库.
>并行实现 – O(n / p) – 非常
快速,需要其他基础设施到位,如果卷是使用的
非常大,预计会增长,这是一个主要的表现
瓶颈.
(另请注意,intersectSortedArrays中的函数本质上是一个修改的合并连接,其中过滤器在连接期间完成,您可以稍后过滤,尽管内存容量略有增加).
最后的想法
事实上,我怀疑大多数现代商业RDBMS在实现联接时提供线程并行性,所以Hadoop版本提供的是机器级并行性(分发).从设计的角度来看,也许一个很好的简单的解决方案就是将数据放在数据库上,A和B上的索引(有效排序数据),并使用sql内部连接.
