java - 如何相交两个排序的整数数组而不重复？

Question

这是我用作编程练习的面试问题。

输入两个按递增顺序排序的整数数组A和B，大小分别为N和M

输出:一个按递增顺序排序的整数数组 C，其中包含同时出现在 A 和 B 中的元素

约束C中不允许重复

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

谢谢大家的回答!总而言之，解决这个问题有两种主要方法:

我最初的解决方案是保留两个指针，每个数组一个，并从左到右交替扫描数组，同时挑选出匹配的元素。因此，当我们一个数组的当前元素大于第二个数组时，我们不断递增第二个数组的指针，直到找到当前第一个数组元素或越过它(找到一个更大的数组)。我将所有匹配项保存在一个单独的数组中，一旦我们到达任一输入数组的末尾就会返回该数组。

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

我已经实现了这两种方法并进行了实验以了解两者的比较(有关详细信息，请参见 here)。当 M 大约是 N 的 70 倍时，当 N 有 100 万个元素时，二分搜索方法似乎会获胜。

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

从概念上讲，它与您的相似，但包含一些简化。

我认为您无法改进时间复杂度。

编辑:我试过这段代码，它通过了你所有的单元测试。