更快的算法在两个数组之间找到唯一元素？编辑：

arrays algorithm java

2022-08-31 16:44:47

编辑：对于任何对这个问题不熟悉的人，我已经发布了一个答案，澄清了发生了什么。被接受的答案是我觉得最好回答我最初发布的问题的答案，但有关更多详细信息，请参阅我的答案。

注意：此问题最初是伪代码和使用的列表。我已经将其改编为Java和数组。因此，虽然我很想看到任何使用Java特定技巧的解决方案（或任何语言的技巧！），但请记住，最初的问题是与语言无关的。

问题

假设有两个未排序的整数数组和，允许元素重复。它们是相同的（相对于包含的元素），除了其中一个数组具有额外的元素。例如：ab

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

因此，两者在概念上都在做同样的事情。给定长度为 m 且长度为 n，则两种解的运行时间为 O（m + n）。ab

问题

后来我和我的老师聊了聊，他暗示有一种更快的方法可以做到这一点。老实说，我不明白如何;要找出一个元素是否唯一，似乎你至少必须查看每个元素。至少是O（m + n）...右？

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

答案 1

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

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

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

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

答案 2

好了，我们开始吧...向任何期望更快解决方案的人道歉。事实证明，我的老师和我在一起玩得很开心，我完全错过了他所说的话的重点。

我应该首先澄清一下我的意思：

他暗示有一种更快的方法可以做到这一点。

我们谈话的要点是：他说我的XOR方法很有趣，我们讨论了一段时间，讨论我如何找到我的解决方案。他问我是否认为我的解决方案是最佳的。我说我做到了（出于我在问题中提到的原因）。然后他问我，“你确定吗？”他脸上的表情我只能用“自鸣得意”来形容。我犹豫不决，但答应了。他问我是否能想出更好的方法来做到这一点。我当时很想，“你的意思是有更快的方法？”但他没有给我一个直接的答案，而是告诉我要考虑一下。我说我会的。

所以我想了想，确定我的老师知道一些我不知道的事情。在一天没有想出任何东西之后，我来到了这里。

我的老师真正希望我做的是捍卫我的解决方案是最佳的，而不是试图找到更好的解决方案。正如他所说：创建一个好的算法是容易的部分，困难的部分是证明它是有效的（而且它是最好的）。他认为我花了这么多时间在Find-A-Better-Way Land上，而不是花更少的时间制定一个简单的O（n）证明，这很有趣（我们最终这样做了，如果你有兴趣，请参阅下文）。

所以我想，这里学到了很大的教训。我将接受Shashank Gupta的答案，因为我认为它确实设法回答了最初的问题，即使这个问题是有缺陷的。

我会给你们留下一个整洁的小Python单行本，我在输入证明时发现了。它没有更有效率，但我喜欢它：

def getUniqueElement(a, b):
    return reduce(lambda x, y: x^y, a + b)

一个非常非正式的“证明”

让我们从问题中的原始两个数组开始，然后：ab

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

我们在这里说较短的数组有长度，那么较长的数组必须有长度。证明线性复杂性的第一步是将数组附加到第三个数组中（我们称之为）：nn + 1c

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

它有长度。为什么这样做？好吧，现在我们完全有另一个问题：找到出现奇数次的元素（从这里开始，“奇数次”和“唯一”被认为是同一回事）。这实际上是一个非常受欢迎的面试问题，显然是我的老师对他的问题的想法，所以现在我的问题有一些实际意义。万岁！2n + 1c

让我们假设有一个算法比O（n）更快，例如O（log n）。这意味着它只会访问的某些元素。例如，O（log n）算法可能只需要检查示例数组中元素的 log（13） ~ 4 个元素即可确定唯一元素。我们的问题是，这可能吗？c

首先，让我们看看我们是否可以删除任何元素（通过“删除”，我的意思是不必访问它）。如果我们删除2个元素，以便我们的算法只检查长度的子数组，怎么样？这仍然是线性复杂性，但如果我们可以做到这一点，那么也许我们可以进一步改进它。c2n - 1

因此，让我们选择两个完全随机的元素来删除。实际上，这里可能会发生几件事，我将总结为一些案例：c

// Case 1: Remove two identical elements
{6, 5, 6, 3, 4, 2, 5, 7, 2, 3, 4};

// Case 2: Remove the unique element and one other element
{6, 6, 3, 4, 2, 5, 6, 6, 2, 3, 4};

// Case 3: Remove two different elements, neither of which are unique
{6, 5, 6, 4, 2, 5, 7, 6, 6, 3, 4};

我们的阵列现在是什么样子的？在第一种情况下，7 仍然是唯一元素。在第二种情况下，有一个新的唯一元素 5。在第三种情况下，现在有3个独特的元素...是的，那里完全是一团糟。

现在我们的问题变成了：我们能否仅仅通过观察这个子阵列来确定其独特元素？在第一种情况下，我们看到 7 是子数组的唯一元素，但我们不能确定它也是的唯一元素;删除的两个元素也可以是7和1。类似的论点也适用于第二种情况。在案例 3 中，对于 3 个唯一元素，我们无法分辨出哪两个是非唯一元素。ccc

很明显，即使有访问，也没有足够的信息来解决问题。因此，最佳解决方案是线性解决方案。2n - 1

当然，真正的证明将使用归纳法而不是使用逐例证明，但我会把它留给其他人:)