更快的算法找出两个阵列之间独特的元素？ [英] Faster algorithm to find unique element between two arrays?

问题描述

修改：对于任何新的这个问题，我已经发布了答案澄清了事情的原委。该接受的答案是一个我觉得最好的回答我的问题作为最初发布，但对于进一步详情，请参阅我的答案。

EDIT: For anyone new to this question, I have posted an answer clarifying what was going on. The accepted answer is the one I feel best answers my question as originally posted, but for further details please see my answer.

注意：这个问题本来是假性code和使用的列表。我已经适应了它的Java和数组。因此，虽然我很想看到，使用Java特定的技巧（或技巧，任何语言的这个问题！）的任何解决方案，只记得最初的问题是语言无关。

NOTE: This problem was originally pseudocode and used lists. I have adapted it to Java and arrays. So while I'd love to see any solutions that use Java-specific tricks (or tricks in any language for that matter!), just remember that the original problem is language-independent.

假设有两个未排序整数数组 A 和 B ，与元素的重复允许的。他们是（以包含的元素与尊重）相同的除了的阵列中的一个有一个额外的元素。作为一个例子：

Let's say that there are two unsorted integer arrays a and b, with element repetition allowed. They are identical (with respect to contained elements) except one of the arrays has an extra element. As an example:

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

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

Design an algorithm that takes as input these two arrays and outputs the single unique integer (in the above case, 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;
}

官方的解决方案$ P psented类$：

The "official" solution presented in class:

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）。

So, both are conceptually doing the same thing. And given that a is of length m and b is of length n, then both solutions have running time of O(m + n).

后来我得到了我的老师讲，他暗示，有这样做的偶的更快的方式。老实说，我不明白如何;以找出是否一个元素的是的独特好像你必须至少看每一个元素。在这至少O（M + N）...对吧？

I later got to talking with my teacher and he hinted that there was an even faster way of doing it. Honestly I don't see how; to find out whether an element is unique it seems you'd have to at least look at every element. At that's at least O(m + n)...right?

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

So is there a faster way? And if so, what is it?

推荐答案

这可能是最快的，你可以使用HotLick的建议的意见在Java中做到这一点。它使假设 b.length个==则为a.length + 1 所以b是较大的阵列与额外的独一无二的元素。

This is probably the fastest you can do it in Java using HotLick's suggestion in the comments. It makes the assumption that b.length == a.length + 1 so b is the larger array with the extra "unique" element.

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），虽然只有环/分配可以减少开销。

Even if the assumption cannot be made, you can easily expand it to include the case where either a or b can be the larger array with the unique element. It's still O(m+n) though and only loop/assignment overhead is reduced.

由于语言的实现细节，这仍然是（奇怪）做在CPython的最快的方法。

Due to details of language implementation, this is still (surprisingly) the fastest way to do it in 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 ^一个确实是快在Python比速记沤^ = A 。还遍历一个循环中的元素比遍历索引，然后在Python使得标操作多快得多。这就是为什么这个code是比我的previous方法，其中我试图复制Java的快很多。

I have tested this with the timeit module and found some interesting results. It turns out that the longhand ret = ret ^ a is indeed faster in Python than the shorthand ret ^= a. Also iterating over the elements of a loop is much much faster than iterating over the indexes and then making subscript operations in Python. That is why this code is much faster than my previous method where I tried to copy Java.

我想这个故事的寓意是，没有正确的答案，因为这个问题是伪造的反正。由于OP下面另一个回答说，事实证明，你真的不能去任何比O（M + N）快就这个问题和他的老师才开他的腿。因此，问题简化为寻找遍历两个数组的所有元素最快的方法，积累所有的人的XOR。这意味着它完全依赖于语言实现的，你必须做一些测试和玩弄取得任何实现您使用的是真正的最快的解决方案，因为整体算法也不会改变。

I guess the moral of the story is that there is no correct answer because the question is bogus anyways. As the OP noted in another answer below, it turns out you can't really go any faster than O(m+n) on this and his teacher was just pulling his leg. Thus the problem reduces to finding the fastest way to iterate over all elements in the two arrays and accumulating the XOR of all of them. And this means it's entirely dependent on language implementation, and you have to do some testing and playing around to get the true "fastest" solution in whatever implementation you are using, because the overall algorithm will not change.

这篇关于更快的算法找出两个阵列之间独特的元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！