如何交叉两个排序的整数数组没有重复？
这是我作为编程练习使用的面试问题。
输入：分别按递增顺序和不同大小N和M的两个排序整数数组A和B.
输出：按升序排序的排序整数数组C，包含出现在A和B中的元素
对比： C中不允许重复
示例：对于输入A = {3,6,8,9}和B = {4,5,6,9,10,11}，输出应为C = {6,9}
谢谢你的回答，全部！ 总而言之，这个问题有两种主要方法：
我最初的解决方案是保留两个指针，每个指针对应一个arrays，并从左到右交替扫描arrays，同时挑选出匹配的元素。 因此，当我们一个数组的当前元素大于第二个数组时，我们继续递增第二个数组的指针，直到我们找到当前的第一个数组元素或者超过它（找到一个更大的数组）。 我保持所有匹配在一个单独的数组中，一旦我们到达任一输入数组的末尾就返回。
我们可以这样做的另一种方法是线性扫描其中一个数组，同时使用二进制搜索在第二个数组中查找匹配。 这将意味着O（N * log（M））时间，如果我们扫描A并且对于其N个元素中的每一个在B上进行二进制搜索（O（log（M））时间）。
我已经实现了两种方法，并进行了一项实验，看看这两种方法的比较（详情请参见此处 ）。 当N具有100万个元素时，当M大约是N的70倍时，二元搜索方法似乎获胜。
这个问题本质上减少了一个连接操作，然后是一个过滤操作（删除重复项，只保留内部匹配）。
由于输入都已经排序，因此可以通过合并连接有效地实现连接 ，其中O（大小（a）+大小（b））。
过滤操作将为O（n），因为连接的输出已排序并且要删除重复项，您只需检查每个元素是否与之前的元素相同。 仅过滤内部匹配是微不足道的，您只需丢弃任何未匹配的元素（外部联接）。
并行性（在连接和filter中）都有机会实现更好的性能。 例如，Hadoop上的Apache Pig框架提供了合并连接的并行实现 。
在性能和复杂性（以及可维护性）之间存在明显的权衡。 所以我想说一个面试问题的好答案确实需要考虑到性能要求。
-
基于集合的比较 – O（nlogn） – 相对较慢，非常简单，如果没有性能问题则使用。 简单胜利。
-
合并连接+filter – O（n） – 快速，容易出现编码错误，如果性能有问题则使用。 理想情况下，尝试利用现有库来执行此操作，或者甚至可以使用数据库（如果适用）。
-
并行实现 – O（n / p） – 非常快，需要其他基础设施，如果卷非常大并且预计会增长，则使用这是一个主要的性能瓶颈。
（另请注意，问题intersectSortedArrays中的函数本质上是一个修改过的合并连接，其中filter在连接期间完成。您可以在没有性能损失的情况下进行过滤，尽管内存占用量略有增加）。
最后的想法。
事实上，我怀疑大多数现代商业RDBMS在其连接实现中提供线程并行性，因此Hadoop版本提供的是机器级并行（分发）。 从设计的角度来看，问题的一个好的，简单的解决方案可能是将数据放在数据库上，索引放在A和B上（有效地排序数据）并使用SQL内连接。
怎么样：
public static int[] intersectSortedArrays(int[] a, int[] b){ int[] c = new int[Math.min(a.length, b.length)]; int ai = 0, bi = 0, ci = 0; while (ai < a.length && bi < b.length) { if (a[ai] < b[bi]) { ai++; } else if (a[ai] > b[bi]) { bi++; } else { if (ci == 0 || a[ai] != c[ci - 1]) { c[ci++] = a[ai]; } ai++; bi++; } } return Arrays.copyOfRange(c, 0, ci); }
从概念上讲，它与您的相似，但包含许多简化。
我不认为你可以改善时间的复杂性。
编辑：我已经尝试过这段代码，它会通过你所有的unit testing。
使用arraylist存储结果。
public ArrayList arrayIntersection(int [] a, int[] b) { int len_a=a.length; int len_b=b.length; int i=0; int j=0; ArrayList alist=new ArrayList(); while(ib[j]) j++; else if(a[i]==b[j]) { alist.add(a[i]); i++; j++; } } return alist; }
如果您正在使用’Integer’（对象）数组并且想要使用java API方法，则可以检查以下代码。 请注意，下面的代码可能具有更多的复杂性（因为它使用从一个数据结构到其他的一些转换逻辑）和内存消耗（因为使用对象）而不是基本方法，如上所列。 我刚尝试过（ 耸耸肩 ）：
public class MergeCollections { public static void main(String[] args) { Integer[] intArray1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; Integer[] intArray2 = new Integer[] {2, 3, 5, 7, 8, 11, 13}; Set intSet1 = new TreeSet (); intSet1.addAll(Arrays.asList(intArray1)); intSet1.addAll(Arrays.asList(intArray2)); System.out.println(intSet1); } }
并输出：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13]
此外，请检查此链接： Algolist – Algo合并排序的数组
编辑 ：将HashSet更改为TreeSet
编辑2 ：现在问题被编辑和清除，我正在添加一个简单的解决方案来查找交集：
public class Intersection { public static void main(String[] args) { Integer[] intArray1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; Integer[] intArray2 = new Integer[] {2, 3, 5, 7, 8, 11, 13}; List list1 = Arrays.asList(intArray1); Set commonSet = new TreeSet (); for(Integer i: intArray2) { if(list1.contains(i)) { commonSet.add(i); } } System.out.println(commonSet); } }
我不知道以这种方式解决问题是否是一个好主意：
说
A,B are 1 based arrays A.length=m B.length=n
1）初始化一个数组C，其长度为min（m，n）
2）通过检查第一个和最后一个元素，只关注公共部分。 这里可以使用二进制搜索。 举个例子来保存一些单词：
A[11,13,15,18,20,28,29,80,90,100.........300,400] ^ ^ B[3,4,5,6,7.8.9.10.12,14,16,18,20,..400.....9999] ^ ^ then we need only focus on A[start=1](11)-A[end=m](400) and B[start=9](12)-B[end](400)
3）。 比较两个arrays的范围 (end-start) 。 从A[start] ~ A[end]为每个元素A[i]取较小范围的数组，比如说A，在B[start,end]进行二进制搜索，
-
如果找到，将元素放入C，将B.start重置为foundIdx + 1，
-
否则B.start设置为最小元素[j]，其中B [j]大于A [i]，以缩小范围
4）继续3）直到处理A [start，end]中的所有元素。
- 通过步骤1，我们可以找到两个Array之间没有交集的情况。
- 当在步骤3中进行二元搜索时，我们将A [i]与A [i-1]进行比较，如果相同，则跳过A [i]。 为了保持C中的元素是唯一的。
这样，更糟糕的情况是lg（n！）if（A和B是否相同）？ 不确定。
平均案例？
这是一个记忆改进：
最好将结果（C）存储在动态结构（如链表）中，并在找到相交元素后创建数组（与数组r完全相同）。 如果你有一个非常大的A和B数组并且期望相比较少的公共元素（为什么在你只需要少量时搜索大量的连续内存？），这种技术会特别好。
编辑：我会改变的另一件事，这可能只是有点挑剔，是当我手头已知最坏情况的迭代次数时，我会避免使用未绑定的循环。