在两个数组之间查找唯一元素的更快算法？

在两个数组之间查找唯一元素的更快算法？

在注释中使用HotLick的建议，这可能是最快的Java处理方法。它假设

b.length == a.length + 1

so
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

模块对此进行了测试，并发现了一些有趣的结果。事实证明，

ret = ret ^ a

Python中的速记确实比速记更快

ret^= a

。同样，遍历循环的元素比遍历索引然后在Python中进行下标 *** 作要快得多。这就是为什么此代码比我以前尝试复制Java的方法快得多的原因。

我想这个故事的寓意是没有正确的答案，因为无论如何这个问题都是虚假的。正如OP在下面的另一个答案中指出的那样，事实证明，您这样做的真正速度不能超过O（m +
n），而他的老师只是在拉他的腿。因此，问题减少到寻找最快的方法来迭代两个数组中的所有元素并累加所有元素的XOR。这意味着它完全取决于语言的实现，并且您必须进行一些测试和测试才能在使用的任何实现中获得真正的“最快”解决方案，因为整个算法不会改变。