给定一个数组，其中每个元素出现两次，我必须找到数组中哪两个数字只出现一次。最大的额外内存是O(1)。
我找到了这个神奇的解决方案。https: /medium.com@gurupad93two -numbers -that -appear -once -b89e92a9334b。
问题是，我的解决方案应该是 分而治之，我的理解是，我找到的解决方案不是。
我知道如何解决这个问题 分而治之 当出现一次的元素只有一个时。这里，说实话，我就不知道如何对数组进行递归划分了。
有什么建议吗？
非常感谢您
我假设这些数字是正整数。列表的元素数是偶数。你计算平均数，并将列表分成两个子列表，低于平均数和高于平均数。那么要么两个都是奇数元素，要么都是偶数元素。在奇数的情况下，你知道每个子列表中都包含一个单子，你就为每个子列表解决单子问题。在偶数情况下，你知道其中一个子列表没有单子，即是成对的，而另一个子列表有两个单子。你决定哪一个是成对的，并继续研究另一个，递归地解决两个单子问题。
如果整数用标准二进制表示，你可以对所有的整数进行XOR来决定它们是否成对。否则，如果它们是用BCD、浮点或其他代表不是唯一的东西来表示，你可以使用下面的测试：如果且仅当所有元素的乘积是一个平方时，一个整数列表是成对的。计算exp( 12 sum( log xi ) )，如果是积分，则列表是成对的，否则不是。
但链接中的解法诚然比这个好用得多。
选择第一个位。
把这个位子设置的数字和这个位子为零的数字分开。
你可以在快速排序中使用类似partition的例程--找到最左边带一位的数字，找到最右边带零位的数字，交换它们，继续，直到左右索引相遇。
考虑到下一位的情况，处理左边的部分和右边的部分。
用下一个位子递归地做这件事，直到部分大小变成1或2。
在第一种情况下，你已经找到了需要的数字之一。
在第二种情况下，检查数字是否不同。
我希望这些线索可以帮助实现可能的分而治之的方法。
我能够找到一个算法来解决我的问题。
我找到了数组的中位数 然后用分割法把所有较小的元素放在中位数的左边 而所有较大的元素放在右边。
我有一个算法，当出现一次的元素只有一个时，能够返回（对所有元素使用XOR）。如果没有元素只出现一次，XOR结果为0。
我在两个子数组上都运行这个算法，两个选项。
如果算法在一个数组上输出0，那么可以肯定这个元素不在这个子数组中，我们在另一半数组上递归调用这个函数。
如果（也只有当）算法输出两个不同于0的数字，这意味着结果在数组中被分开了。在这种情况下，这两个数字也将是问题的结果。
请注意，除了这两个选项，没有其他选项。
空间复杂度为O(1)
时间复杂度。我们有一些花费O(n)的操作，我们在每次迭代时除以数组的一半，我们得到：
T(n) = T(n2) + O(n) -> (主定理) -> O(n)
这个问题可以用树形结构划分（类似于合并排序的树形结构），每个分区将其元素的xor值返回给父分区。这样，我们就可以得到两个数组中只出现一次的数的xor值。
从问题中可以看出，xor值至少有一个非零位。
让我们假设xor值是 X 及其 i-第-位是非零。
现在我们再把问题按树结构划分，考虑元素，其 i-第-位被设置，用于xor计算。这个值会返回给父节点。根节点将得到元素的xor值，这些元素的 i第-位被设置。我们称这个值为Y。
因此，这两个数字是 Y 和 X xor Y.