在许多情况下，使用 XOR 运算符查找数组中的重复元素会失败

Question

我遇到了一篇文章 如何在洗牌的连续整数数组中找到重复元素？ 但后来意识到这对于许多输入都失败了。

例如：

arr[] = {601,602,603,604,605,605,606,607}

 #include <stdio.h>
int main()
{
int arr[] = {2,3,4,5,5,7};
int i, dupe = 0;
for (i = 0; i < 6; i++) {
    dupe = dupe ^ a[i] ^ i;
}
printf ("%d\n", dupe);
return 0;
}

如何修改此代码以便在所有情况下都可以找到重复元素？

原文由 Snehasish 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

从原始问题：

假设您有一个包含 1001 个整数的数组。整数是随机顺序的，但您知道每个整数都在 1 到 1000（含）之间。此外，每个数字在数组中只出现一次，除了一个数字出现两次。

它基本上说，该算法仅在您有连续整数时才有效， 从 1 开始，以某个 N 结尾。

如果要将其修改为更一般的情况，则必须执行以下操作：

在数组中找到最小值和最大值。然后计算预期输出（异或最小值和最大值之间的所有整数）。然后计算数组中所有元素的异或。然后对这两件事进行异或，你会得到一个输出。

原文由 usamec 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

请记住 XOR 运算符的这两个属性：

(1) 如果你对一个数字与 0 ( zero ) 进行异或，它会再次返回相同的数字。

意味着 , n ^ 0 = n

(2) 如果你对一个数字本身进行异或，它将返回 0（零）。

意味着 , n ^ n = 0

现在，问题来了：

    Let    Input_arr = { 23 , 21 , 24 , 27 , 22 , 27 , 26 , 25 }

   Output should be 27 ( because 27 is the duplicate element in the Input_arr ).

解决方案 ：

第 1 步：在给定数组中找到“min”和“max”值。这将需要 O(n)。

第 2 步：查找从“min”到“max”（包括）范围内的所有整数的 XOR。

第 3 步：查找给定数组的所有元素的 XOR。

第 4 步：第 2 步和第 3 步的 XOR 将给出所需的重复编号。

描述 ：

 Step1 : min = 21 , max = 27

Step 2 : Step2_result = 21 ^ 22 ^ 23 ^ 24 ^ 25 ^ 26 ^ 27 = 20

Step 3 : Step3_result = 23 ^ 21 ^ 24 ^ 27 ^ 22 ^ 27 ^ 26 ^ 25 = 15

Step 4 : Final_Result = Step2_result ^ Step3_result = 20 ^ 15 = 27

But , How Final_Result calculated the duplicate number ?

Final_Result = ( 21 ^ 22 ^ 23 ^ 24 ^ 25 ^ 26 ^ 27 ) ^ ( 23 ^ 21 ^ 24 ^ 27 ^ 22 ^ 27 ^ 26 ^ 25 )

Now , Remember above two properties : n ^ n = 0 AND n ^ 0 = n

So , here ,

Final_Result = ( 21 ^ 21 ) ^ ( 22 ^ 22 ) ^ ( 23 ^ 23 ) ^ ( 24 ^ 24 ) ^ ( 25 ^ 25 ) ^ ( 26 ^ 26 ) ^ ( 27 ^ 27 ^ 27 )

             = 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 0 ^ ( 27 ^ 0 ) ( property applied )

             = 0 ^ 27 ( because we know 0 ^ 0 = 0 )

             = 27 ( Required Result )

原文由 Vishal Srivastav 发布，翻译遵循 CC BY-SA 4.0 许可协议