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

Question

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

注意:此问题最初是伪代码和使用列表.我已将它改编为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)......对吗？

那么有更快的方法吗？如果是这样,它是什么？

Answer 1

这可能是您在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 ^ aPython的速记确实比速记更快ret ^= a.迭代遍历循环元素比迭代索引然后在Python中进行下标操作要快得多.这就是为什么这段代码比我之前尝试复制Java的方法快得多的原因.

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

Answer 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)

一个非常非正式的"证明"

让我们从问题的原始两个数组开始,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访问,也没有足够的信息来解决问题.因此,最佳解决方案是线性解决方案.

当然,真正的证据会使用归纳而不是使用示例,但我会把它留给别人:)

Answer 3

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