algorithm - 找出三个出现次数为偶数的唯一数字

Question

给出了一个整数数组。在该数组中，3 个唯一数字的出现次数为偶数。休息只有一次。有什么方法可以使用 XOR 逻辑找到这些数字。给定的数组也是 n+3 个元素。数组的所有元素都在 1 到 n 的范围内。

例如:arr= {4, 2, 4, 5, 2, 3, 1, 5} 其中 n = 5 这里偶数出现的唯一数字是 2、4 和 5

我对数组编号进行了异或运算，同时对范围 1 到 n 进行了异或运算。这给出了一个数字，它是最后三个唯一数字的 XOR 的答案。如果有两个数字，我们可以检查设置位并继续查找数字。但是三个数字呢？有什么办法可以做到这一点。

我知道散列可以用来解决问题。我正在寻找 XOR 方法来解决问题。

Answer 1

Xor 可以帮助你，因为:

XOR (Exclusive Or) truth table:
           A    B   XOR
           0    0    0
           1    0    1
           0    1    1
           1    1    0 

所以你可以做的是:

A. Divide the elements that are occurring more than ones to sets
   of the same value 
B. Then xor all elements in each of those sets
C. If the result is zero than you can return that element to the end set

如果您只需要 3 个数字，而不是前一组的大小为 3 时，您可以返回它，但您可以使用此逻辑来计算组中任意偶数个元素。