如何交叉两个排序的整数数组没有重复？

Question

这是我作为编程练习使用的面试问题.

输入:分别按递增顺序和不同大小N和M的两个排序整数数组A和B.

输出:按升序排序的排序整数数组C,包含出现在A和B中的元素

对比: C中不允许重复

示例:对于输入A = {3,6,8,9}且B = {4,5,6,9,10,11},输出应为C = {6,9}

谢谢你的回答,全部!总而言之,这个问题有两种主要方法:

我最初的解决方案是保留两个指针,每个指针对应一个数组,并从左到右交替扫描数组,同时选择匹配的元素.因此,当我们一个数组的当前元素大于第二个数组时,我们继续递增第二个数组的指针,直到我们找到当前的第一个数组元素或者超过它(找到一个更大的数组).我保持所有匹配在一个单独的数组中,一旦我们到达任何一个输入数组的末尾就返回.

我们可以做到这一点的另一种方法是线性扫描其中一个数组,同时使用二进制搜索在第二个数组中查找匹配.这将意味着O(N*log(M))时间,如果我们扫描A并且对于其N个元素中的每一个在B上进行二进制搜索(O(log(M))时间).

我已经实现了两种方法,并进行了一项实验,看看这两种方法的比较(详情请参见此处).当N具有100万个元素时,当M大约是N的70倍时,二元搜索方法似乎获胜.

Answer 1

怎么样:

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); 
}

从概念上讲,它与您的相似,但包含许多简化.

我不认为你可以改善时间的复杂性.

编辑:我已经尝试过这段代码,它通过了所有的单元测试.

Answer 2

这个问题本质上减少了一个连接操作,然后是一个过滤操作(删除重复项,只保留内部匹配).

由于输入都已经排序,因此可以通过合并连接有效地实现连接,其中O(大小(a)+大小(b)).

该过滤器操作将是O(N),因为加入输出的排序和删除重复所有你需要做的就是检查每一个元素都是一样收到一个.仅过滤内部匹配是微不足道的,您只需丢弃任何未匹配的元素(外部联接).

并行性(在连接和过滤器中)都有机会实现更好的性能.例如,Hadoop上的Apache Pig框架提供了合并连接的并行实现.

在性能和复杂性(以及可维护性)之间存在明显的权衡.所以我想说一个面试问题的好答案确实需要考虑到性能要求.

• 基于集合的比较 - O(nlogn) - 相对较慢,非常简单,如果没有性能问题则使用.简单胜利.

• 合并连接+过滤器 - O(n) - 快速,容易出现编码错误,如果性能有问题则使用.理想情况下,尝试利用现有的库来执行此操作,或者甚至可以使用数据库(如果适用).

• 并行实现 - O(n/p) - 非常快,需要其他基础架构,如果卷非常大并且预计会增长,则使用这是一个主要的性能瓶颈.

(另请注意,问题intersectSortedArrays中的函数本质上是一个修改过的合并连接,其中过滤器在连接期间完成.您可以在没有性能损失的情况下进行过滤,尽管内存占用量略有增加).

最后的想法.

事实上,我怀疑大多数现代商业RDBMS在其连接实现中提供线程并行性,因此Hadoop版本提供的是机器级并行(分发).从设计的角度来看,问题的一个好的,简单的解决方案可能是将数据放在数据库上,索引A和B(有效地排序数据)并使用SQL内连接.