一尘不染

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

algorithm

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

注意
：此问题最初是伪代码和使用的列表。我已经将其适应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）…对吗？

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

阅读 204

2020-07-28

共1个答案

一尘不染

在注释中使用HotLick的建议，这可能是最快的Java处理方法。它假设b.length == a.length + 1so
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 ^ aPython中的速记确实比速记更快ret ^= a。同样，遍历循环的元素比遍历索引然后在Python中进行下标操作要快得多。这就是为什么此代码比我以前尝试复制Java的方法快得多的原因。

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

2020-07-28