小编use*_*214的帖子

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

找到数组的对称差异

输入:两个整数数组

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

测试用例:

输入:

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

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

Run Code Online (Sandbox Code Playgroud)

输出:

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

Run Code Online (Sandbox Code Playgroud)

我提出的方法是

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

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

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

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