找出只出现一次的两个数字 - 分而治之
Find the two numbers that appear only once - divide and conquer
给定一个数组，其中每个元素出现两次，我必须找出数组中哪两个数字只出现一次。最大附加内存为 O(1).
我找到了这个惊人的解决方案：https://medium.com/@gurupad93/two-numbers-that-appear-once-b89e92a9334b
问题是我的解决方案应该是分而治之，而我的理解是我找到的解决方案不是。
我知道如何在出现一次的元素只有一个的情况下用分而治之解决这个问题。在这里，老实说，我不知道如何递归划分数组。
有什么建议吗？
非常感谢！
选择第一位。
将设置了该位的数字与设置了该位的数字分开。
你可以在快速排序中使用类似分区的例程 - 找到最左边的一位数字，找到最右边的零位数字，交换它们，继续直到左右索引相遇。
处理左边和右边的部分，考虑下一位。
对下一位递归执行此操作，直到部分大小变为 1 或 2。
在第一种情况下，您找到了一个需要的号码。
在第二种情况下检查数字是否不同。
我希望这些线索可能有助于实现可能的分而治之方法。
我假设数字是正整数。该列表具有偶数个元素。您计算平均值并将列表分成两个子列表，低于和高于平均值。那么要么两者都有奇数个元素，要么都是偶数。在奇怪的情况下，您知道每个子列表包含一个单例，并且您解决了每个子列表的单例问题。在偶数情况下，您知道其中一个子列表没有单例，即配对，而另一个有两个。你决定哪一个配对并继续处理另一个，递归地解决双单例问题。
如果整数以标准二进制表示，您可以对它们进行异或运算以确定它们是否配对。否则，如果它们以 BCD、浮点数或代表不唯一的任何形式表示，则可以使用以下测试：
当且仅当所有元素的乘积是正方形时，整数列表才是成对的。计算 exp( 1/2 sum( log xi ) ) 如果它是整数，则列表是成对的，否则不是。
但是 link 中的解决方案比这要好得多。
我找到了解决我的问题的算法：
我找到数组的中位数并使用分区将所有较小的元素放在中位数的左侧，将所有较大的元素放在右侧。
我有一个算法能够 return 当出现一次的元素只有一个时（对所有元素使用 XOR）。如果没有只出现一次的元素，则异或结果为0。
我运行这个算法在两个子数组上，两个选项：
如果算法在一个数组上输出0，那么肯定该元素不在这个子数组中，我们在另一半上递归调用该函数。
如果（且仅当）算法输出两个不为 0 的数字，这意味着结果在数组中分开了。在这种情况下，这两个数字也将是问题的结果。
请注意，除了这两个，没有其他选项。
Space 复杂度为 O(1)
时间复杂度：我们有一些成本为 O(n) 的操作，我们在每次迭代时将数组分成一半，我们得到：
T(n) = T(n/2) + O(n) -> (主定理) -> O(n)
问题可以按树结构划分（类似于归并排序的树结构），每个分区returns其元素与父节点的异或值。这样我们就得到了数组中只出现一次的两个数的异或值。
从问题中可以看出，异或值至少有一个非零位。
让我们假设异或值是 X 并且它的第 i 位是非零的。
现在我们再次将问题划分为树结构，并考虑第 i 位已设置的元素，用于异或计算。该值返回给父级。根节点将获得设置了第 i 位的元素的异或值。让我们称这个值为 Y.
因此，这两个数字是 Y 和 X xor Y。
给定一个数组，其中每个元素出现两次，我必须找出数组中哪两个数字只出现一次。最大附加内存为 O(1).
我找到了这个惊人的解决方案：https://medium.com/@gurupad93/two-numbers-that-appear-once-b89e92a9334b
问题是我的解决方案应该是分而治之，而我的理解是我找到的解决方案不是。
我知道如何在出现一次的元素只有一个的情况下用分而治之解决这个问题。在这里，老实说，我不知道如何递归划分数组。
有什么建议吗？
非常感谢！
选择第一位。
将设置了该位的数字与设置了该位的数字分开。
你可以在快速排序中使用类似分区的例程 - 找到最左边的一位数字，找到最右边的零位数字，交换它们，继续直到左右索引相遇。
处理左边和右边的部分，考虑下一位。
对下一位递归执行此操作，直到部分大小变为 1 或 2。
在第一种情况下，您找到了一个需要的号码。
在第二种情况下检查数字是否不同。
我希望这些线索可能有助于实现可能的分而治之方法。
我假设数字是正整数。该列表具有偶数个元素。您计算平均值并将列表分成两个子列表，低于和高于平均值。那么要么两者都有奇数个元素，要么都是偶数。在奇怪的情况下，您知道每个子列表包含一个单例，并且您解决了每个子列表的单例问题。在偶数情况下，您知道其中一个子列表没有单例，即配对，而另一个有两个。你决定哪一个配对并继续处理另一个，递归地解决双单例问题。
如果整数以标准二进制表示，您可以对它们进行异或运算以确定它们是否配对。否则，如果它们以 BCD、浮点数或代表不唯一的任何形式表示，则可以使用以下测试： 当且仅当所有元素的乘积是正方形时，整数列表才是成对的。计算 exp( 1/2 sum( log xi ) ) 如果它是整数，则列表是成对的，否则不是。
但是 link 中的解决方案比这要好得多。
我找到了解决我的问题的算法：
我找到数组的中位数并使用分区将所有较小的元素放在中位数的左侧，将所有较大的元素放在右侧。
我有一个算法能够 return 当出现一次的元素只有一个时（对所有元素使用 XOR）。如果没有只出现一次的元素，则异或结果为0。
我运行这个算法在两个子数组上，两个选项：
如果算法在一个数组上输出0，那么肯定该元素不在这个子数组中，我们在另一半上递归调用该函数。
如果（且仅当）算法输出两个不为 0 的数字，这意味着结果在数组中分开了。在这种情况下，这两个数字也将是问题的结果。
请注意，除了这两个，没有其他选项。
Space 复杂度为 O(1)
时间复杂度：我们有一些成本为 O(n) 的操作，我们在每次迭代时将数组分成一半，我们得到：
T(n) = T(n/2) + O(n) -> (主定理) -> O(n)
问题可以按树结构划分（类似于归并排序的树结构），每个分区returns其元素与父节点的异或值。这样我们就得到了数组中只出现一次的两个数的异或值。
从问题中可以看出，异或值至少有一个非零位。
让我们假设异或值是 X 并且它的第 i 位是非零的。
现在我们再次将问题划分为树结构，并考虑第 i 位已设置的元素，用于异或计算。该值返回给父级。根节点将获得设置了第 i 位的元素的异或值。让我们称这个值为 Y.
因此，这两个数字是 Y 和 X xor Y。