java - 更快的算法来找到两个数组之间的唯一元素？

Question

编辑:对于这个问题的新手，我已经发布了一个答案来澄清发生了什么。接受的答案是我认为最能回答我最初发布的问题的答案，但有关更多详细信息，请参阅我的答案。

注意:这个问题最初是伪代码和使用列表。我已经将它改编为 Java 和数组。因此，虽然我希望看到任何使用 Java 特定技巧(或任何语言中的技巧!)的解决方案，但请记住，原始问题与语言无关。

问题

假设有两个未排序的整数数组 a 和 b，允许元素重复。它们是相同的(就包含的元素而言)除了其中一个数组有一个额外的元素。举个例子:

int[] a = {6, 5, 6, 3, 4, 2};
int[] b = {5, 7, 6, 6, 2, 3, 4};

设计一种算法，将这两个数组作为输入并输出单个唯一整数(在上述情况下为 7)。

解决方案(到目前为止)

我想出了这个:

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    for (int i = 0; i < a.length; i++) {
        ret ^= a[i];
    }
    for (int i = 0; i < b.length; i++) {
        ret ^= b[i];
    }
    return ret;
}

类里面呈现的“官方”解决方案:

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    for (int i = 0; i < a.length; i++) {
        ret += a[i];
    }
    for (int i = 0; i < b.length; i++) {
        ret -= b[i];
    }
    return Math.abs(ret);
}

所以，两者在概念上都在做同样的事情。并且鉴于 a 的长度为 m 而 b 的长度为 n，那么这两种解决方案的运行时间都是 O(m + n)。

问题

我后来和我的老师交谈，他暗示有一种更更快的方法。老实说，我不明白怎么做；要确定一个元素 是否 是唯一的，您似乎至少必须查看每个元素。至少是 O(m + n)...对吗？

那么有没有更快的方法？如果是这样，它是什么？

Answer 1

这可能是您在 Java 中使用 HotLick 在评论中的建议可以做到的最快速度。它假设 b.length == a.length + 1 所以 b 是具有额外“唯一”元素的较大数组。

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    int i;
    for (i = 0; i < a.length; i++) {
        ret = ret ^ a[i] ^ b[i];
    }
    return ret ^ b[i];
}

即使无法做出假设，您也可以轻松地将其扩展为包含 a 或 b 可以是具有唯一元素的较大数组的情况。虽然它仍然是 O(m+n)，但只有循环/分配开销减少了。

编辑:

由于语言实现的细节，这仍然是(令人惊讶的)在 CPython 中最快的方法。

def getUniqueElement1(A, B):
    ret = 0
    for a in A: ret = ret ^ a
    for b in B: ret = ret ^ b
    return ret

我用 timeit 模块对此进行了测试，发现了一些有趣的结果。事实证明，在 Python 中，速记 ret = ret ^ a 确实比速记 ret ^= a 快。此外，迭代循环的元素比迭代索引然后在 Python 中进行下标操作要快得多。这就是为什么这段代码比我之前尝试复制 Java 的方法快得多的原因。

我想这个故事的寓意是没有正确答案，因为这个问题无论如何都是假的。正如 OP 在下面的另一个答案中指出的那样，事实证明你真的不能比 O(m+n) 快，他的老师只是在拉他的腿。因此，问题归结为找到迭代两个数组中所有元素并累积所有元素的 XOR 的最快方法。这意味着它完全依赖于语言实现，您必须进行一些测试和尝试才能在您使用的任何实现中获得真正“最快”的解决方案，因为整体算法不会改变。