algorithm - 找出只出现一次的两个数字——分而治之

Question

给定一个每个元素出现两次的数组，我必须找出数组的哪两个数字只出现一次。最大额外内存为 O(1)。

我找到了这个惊人的解决方案：https ://medium.com/@gurupad93/two-numbers-that-appear-once-b89e92a9334b

问题是我的解决方案应该是分而治之，而我的理解是我找到的解决方案不是。

当出现一次的元素只是一个时，我知道如何通过分而治之来解决这个问题。在这里，老实说，我不知道如何递归地划分数组。

有什么建议么？

太感谢了！

标签： algorithmtime-complexitybit-manipulationdivide-and-conquer

Answer 1

我假设这些数字是正整数。该列表具有偶数个元素。您计算平均值并将列表分为两个子列表，低于和高于平均值。然后要么都有奇数个元素，要么都是偶数。在奇怪的情况下，您知道每个子列表都包含一个单例，并且您解决了每个子列表的单例问题。在偶数情况下，您知道其中一个子列表没有单例，即成对，而另一个有两个。您决定哪一个配对并继续处理另一个，递归地解决两个单例问题。

如果整数以标准二进制表示，您可以对所有整数进行异或以确定它们是否成对。否则，如果它们以 BCD、浮点数或代表不唯一的任何形式表示，则可以使用以下测试：当且仅当所有元素的乘积是平方时，整数列表才成对。计算 exp( 1/2 sum( log xi ) )，如果它是整数，则列表成对，否则不成对。

但是链接中的解决方案无疑比这要好得多。