java – 如何交叉两个没有重复的排序整数数组？
|
这是一个面试问题,我用作编程练习.
输入：两个排序整数数组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) – 如果没有性能问题,相对较慢,非常简单.简单胜利. (另请注意,intersectSortedArrays中的函数本质上是一个修改的合并连接,其中过滤器在连接期间完成,您可以稍后过滤,尽管内存容量略有增加). 最后的想法 事实上,我怀疑大多数现代商业RDBMS在实现联接时提供线程并行性,所以Hadoop版本提供的是机器级并行性(分发).从设计的角度来看,也许一个很好的简单的解决方案就是将数据放在数据库上,A和B上的索引(有效排序数据),并使用SQL内部连接. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |