更快的algorithmfind两个数组之间的唯一元素？
编辑 ：任何新来的这个问题，我已经张贴了一个答案，澄清发生了什么事情。 接受的答案是我最好的回答我最初发布的问题的答案，但进一步的细节请看我的答案。
注 ：这个问题最初是伪代码和使用的列表。 我已经适应了Java和数组。 所以，虽然我很想看到任何使用Java特定技巧的解决scheme（或者任何语言的技巧！），但请记住原始问题是与语言无关的。
问题
假设有两个未sorting的整数数组a和b ，允许元素重复。 它们是相同的（相对于包含的元素）， 除了其中一个数组有一个额外的元素。 举个例子：
int[] a = {6, 5, 6, 3, 4, 2}; int[] b = {5, 7, 6, 6, 2, 3, 4};
devise一个algorithm，将这两个数组作为input，并输出唯一的唯一整数（在上面的例子中是7）。
解决scheme（迄今为止）
我想出了这个：
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; }
课堂上呈现的“官方”解决scheme：
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）。
问题
后来我开始和老师谈话，他暗示说有一个更快的方法。 老实说，我不明白如何; 要找出一个元素是否是唯一的，看起来你至less要看看每一个元素。 那至less是O（m + n）…对吧？
那么有没有更快的方法？ 如果是这样，那是什么？
这可能是最快的，你可以在Java中使用HotLick的build议在评论中。 它使得b.length == a.length + 1所以b是带有额外的“unique”元素的较大数组。
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可以是具有唯一元素的较大arrays的情况。 它仍然是O（M + N），只有循环/分配开销减less。
编辑：
由于语言实现的细节，这仍然是（令人惊讶的）在CPython中最快的方法。
def getUniqueElement1(A, B): ret = 0 for a in A: ret = ret ^ a for b in B: ret = ret ^ b return ret
我用timeit模块testing了这个，发现了一些有趣的结果。 原来， ret = ret ^ a在Python中确实比速记ret ^= a更快。 迭代遍历循环的元素比迭代索引，然后在Python中进行下标操作要快得多。 这就是为什么这个代码比我以前的方法，我试图复制Java快得多。
我想这个故事的寓意是没有正确的答案，因为这个问题是虚假的。 正如OP在下面的另一个答案中指出的那样，事实certificate，你不可能比O（m + n）快得多，他的老师只是拉着他的腿。 因此，问题归结为寻找最快的方法来迭代两个数组中的所有元素并累积所有元素的XOR。 这意味着它完全依赖于语言的实现，而且你必须做一些testing和玩弄，以便在你正在使用的任何实现中获得真正的“最快”解决scheme，因为整体algorithm不会改变。
好吧，我们走吧…对任何期待更快解决scheme的人表示歉意。 事实certificate，我的老师和我一起玩得很开心，我完全错过了他所说的话。
我应该首先澄清我的意思：
他暗示说有一个更快的方法
我们谈话的要点是这样的：他说我的XOR方法很有趣，我们谈了一会儿，谈到我如何解决问题。 他问我是否认为我的解决scheme是最佳的。 我说我是（因为我在我的问题中提到的原因）。 然后他问我：“你确定吗？” 看着他的脸，我只能形容为“自鸣得意”。 我犹豫了，但说是的。 他问我是否能想到一个更好的方法来做到这一点。 我很像，“你的意思是有一个更快的方法？” 但他没有给我一个直接的答案，而是让我思考一下。 我说我会的。
所以我想到了，我的老师肯定知道我没有的东西。 而一天之后没有提出任何事情，我来到了这里。
我的老师真正想要我做的是捍卫我的解决scheme是最佳的， 而不是试图find一个更好的解决scheme。 正如他所说：创build一个很好的algorithm是最简单的部分，最难的部分就是certificate它是有效的（而且是最好的）。 他认为我很花时间在Find-A-Better-Way Land上花费了很多时间，而不是制定一个O（n）的简单certificate，这个certificate花费的时间要less得多（我们结束了，你有兴趣）。
所以我想，在这里学到的重要经验教训。 我会接受Shashank Gupta的回答，因为我认为尽pipe问题是有缺陷的，但它确实能够回答原来的问题。
我会在打字时find一个整齐的小Python单线。 这不是更有效率，但我喜欢它：
def getUniqueElement(a, b): return reduce(lambda x, y: x^y, a + b)
非常非正式的“certificate”
让我们从问题a和b的原始两个数组开始：
int[] a = {6, 5, 6, 3, 4, 2}; int[] b = {5, 7, 6, 6, 2, 3, 4};
这里我们要说的是，较短的数组长度为n ，那么较长的数组必须长度为n + 1 。 certificate线性复杂性的第一步是将数组附加到第三个数组中（我们称之为c ）：
int[] c = {6, 5, 6, 3, 4, 2, 5, 7, 6, 6, 2, 3, 4};
长度2n + 1 。 为什么这样做？ 那么现在我们还有另外一个问题：找出c中出现奇数次的元素（从这里开始“奇数次”和“唯一”就意味着同样的事情）。 这实际上是一个很受欢迎的面试问题 ，显然是我老师对他的问题有了解的地方，所以现在我的问题有一些实际意义。 万岁！
假设有一个比O（n）更快的algorithm，比如O（log n）。 这意味着它只会访问c 一些元素。 例如，一个O（log n）algorithm可能只需要检查我们的例子中的元素的log（13）〜4来确定唯一的元素。 我们的问题是，这可能吗？
首先让我们看看我们是否能够消除任何元素（通过“删除”我的意思是不必访问它）。 如果删除2个元素，那么我们的algorithm只会检查一个长度2n - 1的c的子数组呢？ 这仍然是线性的复杂性，但如果我们能做到这一点，那么也许我们可以进一步改进。
所以，我们随机select两个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.在第三种情况下，现在有三个独特的元素…是的，这是一个总的混乱。
现在我们的问题变成：我们可以通过查看这个子数组来确定c的唯一元素吗？ 在第一种情况下，我们看到7是子阵的独特元素，但我们不能肯定它也是c的独特元素; 这两个被移除的元素可能也只有7和1.对于第二种情况也适用类似的论点。 在情况3中，有三个独特的元素，我们没有办法告诉c哪两个是不唯一的。
很明显，即使是2n - 1访问，也没有足够的信息来解决这个问题。 所以最佳的解决scheme是线性的。
当然，一个真正的certificate会使用归纳，而不是使用certificate的例子，但我会把它留给别人:)
您可以将每个值的计数存储在集合（如数组或散列图）中。 O（n），那么你可以检查其他收集的值，并知道你有一个错过匹配停止。 这可能意味着你只能平均search第二个数组的一半。
这有点快一点 ：
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），但是这个命令并没有说明整个故事。 “官方”解决scheme的循环部分具有大约3 * m + 3 * n的操作，略微更快的解决scheme具有4 * m。
（将循环“i ++”和“i <a.length”作为一个操作）。
-Al。
假设只添加了一个元素，并且数组与开始时相同，则可以按O（log（base 2）n）。
理由是任何数组都要经过二进制searchO（log n）。 除了在这种情况下，您不是在有序数组中search值，您正在search第一个不匹配的元素。 在这种情况下，[n] == b [n]意味着你太低了，a [！] = b [n]意味着你可能太高了，除非[n-1] == b [N-1]。
其余的是基本的二进制search。 检查中间元素，确定哪个分区必须有答案，并对该分区进行子search。
假设有两个未sorting的整数数组a和b，允许元素重复。 它们是相同的 （相对于包含的元素）， 除了其中一个数组有一个额外的元素 。
你可能会注意到，我在你原来的问题中强调了两点，而且我加了一个额外的假设，即这些值是非零的 。
在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);
看到？ 无论多余的元素是什么，你总是可以通过简单地分割它们的长度来了解它。
有了这些陈述，我们不是将给定的整数序列存储为数组的值，而是作为它们的维度 。
无论给出什么较短的整数系列，较长的一个应该只有一个额外的整数。 所以无论整数的顺序如何，没有多余的顺序，这两个multidimensional array的总大小是相同的。 额外的维数乘以更长的大小，除以更短的大小，我们知道什么是额外的整数。
这个解决scheme只适用于这个特殊情况，正如我引用你的问题。 您可能希望将其移植到Java。
这只是一个把戏，因为我认为这个问题本身就是一个窍门。 我们绝对不会将其视为生产解决scheme。
注意，使用O（n + m）表示法是错误的。 只有一个尺寸参数是n（在渐近的意义上，n和n + 1是相等的）。 你应该说O（n）。 [对于m> n + 1，问题是不同的，更具挑战性。]
正如其他人指出的，这是最佳的，因为您必须阅读所有的值。
你所能做的就是减less渐近常数。 由于显而易见的解决scheme已经非常有效，所以几乎没有改进的余地。 （10）中的单个循环可能很难被击败。 通过避开一个分支，展开一点应该会稍微改善一点。
如果您的目标是纯粹的性能，那么您应该转向诸如vector化（使用AXV指令，一次8个整数）等非便携式解决scheme，以及多核或GPGPU上的并行化。 在旧的脏C和一个64位的处理器中，你可以将数据映射到一个64位整数的数组，并且一次对两个元素进行异或运算;）
我认为这是类似的螺母和螺栓问题 。
你可以在O（nlogn）中实现这个。 不知道在这种情况下，是否小于O（n + m）。
没有更快的algorithm。 在问题中提出的是O（n）。 任何算术“技巧”来解决这个问题将需要至less两个数组的每个元素被读取一次，所以我们留在O（n）（或更糟糕的）。
任何在O（n）的实际子集中的search策略（比如O（log n））都需要sorting数组或者其他一些预构build的sorting结构（二叉树，散列）。 所有人类已知的sortingalgorithm至less是O（n * log n）（Quicksort，Hashsort）平均值比O（n）差。
因此，从math的angular度来看，没有更快的algorithm。 可能有一些代码优化，但它们不会在大规模的问题，因为运行时将随着数组的长度而线性增长。
