从3个数组中查找唯一的公共元素

Question

原始问题:
我有3个盒子,每个盒子包含200个硬币,因为只有一个人从所有三个盒子中拨打电话,因此每个盒子里有一个硬币有相同的指纹,其余所有硬币都有不同的指纹.您必须找到所有3个盒子中包含相同指纹的硬币.这样我们就可以找到从所有3个方框中拨打电话的人的指纹.

转换问题:
你有3个数组,每个数组包含200个整数.鉴于这3个数组中只有一个共同元素.找到共同的元素.
请考虑解决此问题,除了平凡的O(1)空间和O(n ^ 3)时间.

Answer 1

如果您首先对所有数组进行排序O(n log n),那么在O(n ^ 3)时间内找到公共元素将非常容易.例如,您可以在对它们进行排序后使用二进制搜索

Answer 2

Pelkonen答案的一些改进:
来自OP的转换问题:

"鉴于这三个阵列中只有一个共同的元素."

我们只需要排序2个数组并找到共同的元素.