59

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

注意：这个问题最初是伪代码和使用列表。我已经将它改编为 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）......对吗？

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

4

9 回答 9

28

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

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

于 2013-10-06T02:56:51.077 回答
14

好的，我们开始......向任何期待更快解决方案的人道歉。原来我的老师和我玩得很开心，我完全没有理解他所说的意思。

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

他暗示有一种更快的方法

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

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

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

所以我想，在这里学到了很多教训。我会接受 Shashank Gupta 的回答，因为我认为它确实能够回答最初的问题，即使这个问题有缺陷。

我会给你们留下一个我在输入证明时发现的简洁的 Python 单行代码。它没有任何效率，但我喜欢它：

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

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

让我们从问题中的原始两个数组开始，a并且b：

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

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

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

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

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

首先让我们看看我们是否可以移除任何元素（通过“移除”我的意思是不必访问它）。如果我们删除 2 个元素，那么我们的算法只检查一个c长度为的子数组2n - 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 个唯一元素……是的，那里一团糟。

现在我们的问题变成了：我们可以c通过查看这个子数组来确定唯一的元素吗？在第一种情况下，我们看到 7 是子数组的唯一元素，但我们不能确定它也是 ; 的唯一元素c。两个删除的元素也可能是 7 和 1。类似的论点适用于第二种情况。在案例 3 中，有 3 个唯一元素，我们无法判断哪两个是非唯一的c。

很明显，即使有2n - 1访问权限，也没有足够的信息来解决问题。所以最优解是线性的。

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

于 2013-10-08T01:26:26.387 回答
7

您可以将每个值的计数存储在集合中，例如数组或哈希映射。O(n) 然后您可以检查其他集合的值，并在您知道有未匹配项时立即停止。这可能意味着您平均只搜索第二个数组的一半。

于 2013-10-05T23:53:54.307 回答
3

这有点快：

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

这是 O(m)，但顺序并不能说明全部。“官方”解决方案的循环部分大约有 3 * m + 3 * n 操作，稍快的解决方案有 4 * m。

（将循环“i++”和“i < a.length”分别算作一个操作）。

-阿尔。

于 2013-10-06T00:50:20.327 回答
1

假设只添加了一个元素，并且数组一开始是相同的，你可以达到 O(log(base 2) n)。

基本原理是任何数组都需要进行二进制搜索 O(log n)。除了在这种情况下，您不是在有序数组中搜索值，而是在搜索第一个不匹配的元素。在这种情况下 a[n] == b[n] 意味着你太低了，而 a[n] != b[n] 意味着你可能太高了，除非 a[n-1] == b [n-1]。

剩下的就是基本的二分查找。检查中间元素，确定哪个部门必须有答案，然后对该部门进行子搜索。

于 2013-10-06T04:41:19.933 回答
1

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

您可能会注意到我在原始问题中强调了两点，并且我添加了一个额外的假设，即这些值是non-zero。

在 C# 中，您可以这样做：

int[, , , , ,] a=new int[6, 5, 6, 3, 4, 2];
int[, , , , , ,] b=new int[5, 7, 6, 6, 2, 3, 4];
Console.WriteLine(b.Length/a.Length);

看？无论额外的元素是什么，您都可以通过简单地划分它们的长度来知道它。

使用这些语句，我们不是将给定的整数系列作为值存储到数组中，而是作为它们的维度。

无论给出较短的整数系列，较长的整数应该只有一个额外的整数。所以无论整数的顺序如何，没有多余的一个，这两个多维数组的总大小是相同的。额外的维度乘以较长的大小，然后除以较短的大小，我们知道额外的整数是多少。

正如我从您的问题中引用的那样，此解决方案仅适用于这种特殊情况。您可能希望将其移植到 Java。

这只是一个技巧，因为我认为问题本身就是一个技巧。我们绝对不会将其视为生产解决方案。

于 2013-10-06T08:37:57.853 回答
1

注意，使用 O(n + m) 表示法是错误的。只有一个大小参数是 n（在渐近意义上，n 和 n+1 相等）。你应该说 O(n)。[对于 m > n+1，问题不同，更具挑战性。]

正如其他人指出的那样，这是最佳选择，因为您必须阅读所有值。

你所能做的就是减少渐近常数。几乎没有改进的余地，因为显而易见的解决方案已经非常有效。（10）中的单循环可能很难被击败。通过避免分支，稍微展开它应该会改善（略微）。

如果您的目标是纯粹的性能，那么您应该转向非便携式解决方案，例如矢量化（使用 AXV 指令，一次 8 个整数）和多核或 GPGPU 上的并行化。在良好的旧脏 C 和 64 位处理器中，您可以将数据映射到 64 位整数数组并一次对元素进行两对异或；）

于 2013-10-09T07:14:46.373 回答
0

我认为这类似于匹配螺母和螺栓问题。

你可以在 O(nlogn) 中实现这一点。不确定在这种情况下是否小于 O(n+m)。

于 2013-10-06T04:49:32.027 回答
0

根本没有更快的算法。问题中提出的那些在 O(n) 中。解决这个问题的任何算术“技巧”都需要至少读取两个数组的每个元素一次，所以我们停留在 O(n) （或更糟）。

任何在 O(n) 的实际子集中的搜索策略（如 O(log n)）都需要排序数组或其他一些预构建的排序结构（二叉树、哈希）。人类已知的所有排序算法平均至少为 O(n*log n) (Quicksort, Hashsort)，比 O(n) 差。

因此，从数学的角度来看，没有更快的算法。可能会有一些代码优化，但它们在大规模上并不重要，因为运行时将随着数组的长度线性增长。

于 2013-10-06T22:46:21.573 回答