查找所有其他元素出现两次的数组中出现一次的元素（不使用 XOR）

Question

我已经尝试解决这个问题很久了，但我似乎无法解决。
问题如下：

给定一个数组 n 个数字，其中所有数字都出现两次，除了一个只出现一次，找出只出现一次的数字。

现在，我在网上找到了很多解决方案，但没有一个满足问题的额外限制。
解决方案应该：

• 以线性时间运行（又名 O(n)）。
• 不使用哈希表。
• 假设计算机只支持比较和算术（加、减、乘、除）。
• 数组中每个数字的位数约为 O(log(n))。

因此，使用 XOR 运算符尝试类似/sf/answers/334079791/的操作是不可能的，因为我们没有 XOR 运算符。由于每个数字的位数大约为 O(log(n))，尝试使用普通算术（逐位）实现 XOR 运算符将需要大约 O(log(n)) 个动作，这将给我们一个整体O(nlog(n)) 的解。

我最接近解决它的是，如果我有办法在线性时间内获得数组中所有唯一值的总和，我可以从总和中减去该总和的两倍以获得（负）仅出现一次的元素的，因为如果出现两次的数字是{A1，A2，...，AK}，而出现一次的数量为x时，则整体的总和为
总和= 2（A1 + ... + AK）+ X
就据我所知，集合是使用哈希表实现的，因此使用它们来查找所有唯一值的总和是不好的。

Answer 1

假设我们有一种方法可以在线性时间内找到精确的中位数并划分数组，这样所有较大的元素都在一侧，而较小的元素在另一侧。通过预期元素数量的奇偶校验，我们可以确定目标元素在哪一侧。现在在我们确定的部分中递归执行此例程。由于每次都将节的大小减半，因此遍历的元素总数不能超过 O(2n) = O(n)。