对称差异b/w未排序数组

Question

我在准备面试时试图解决这个问题.问题如下:

找到数组的对称差异

输入:两个整数数组

输出:一个整数数组,仅出现在一个(不是两个)数组中

测试用例:

输入:

           [ 1, 7, 8, 2, 4, 5 ]

           [ 3, 5, 1, 7, 6, 9 ]

输出:

           [ 8, 2, 4, 3, 6, 9 ]

我提出的方法是

• 蛮力运行两个循环,找到共同的元素,然后打印其余的 - T=O(n2)

• 对两个数组进行排序,并遵循与MergeSort的合并过程类似的策略 - T=O(nlogn)

我想不出O(n)中的任何方法.有没有更低时间复杂度的算法来解决这个问题？

您还可以在c ++/java中建议一些特定于语言的库方法

Answer 1

最快的方法是将第Array一个的所有值放入a HashTable然后执行a contains()以查看第二个值是否Array存在.这将为您提供预期的时间复杂度O(n)