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

Question

我在准备面试的时候尝试解决这个问题。问题如下:

Find the Symmetric Difference of Arrays

Input: two arrays of integers

Output: one array of integers which occur in only one (not both) arrays

Test case:

Input:

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

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

Output:

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

我想到的方法是

• Brute for of 运行两个循环，找到共同元素，然后打印其余元素 - T=O(n2)

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

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

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

Answer 1

最快的方法是把第一个Array的所有值放到一个HashTable中，然后做一个contains()看看是否第二个 Array 的值存在。这将为您提供 O(n)

的预期时间复杂度