在许多情况下,使用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;
}

如何修改此代码,以便可以找到所有案例的重复元素？

Answer 1

来自原始问题:

假设您有一个1001整数的数组.整数是随机顺序,但您知道每个整数在1到1000之间(包括1和1000).此外,每个数字在数组中只出现一次,但一个数字除外,它出现两次.

它基本上说,只有当你有连续的整数时,该算法才有效,从1开始,以N结尾.

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

查找数组中的最小值和最大值.然后计算预期输出(xor最小值和最大值之间的所有整数).然后计算数组中所有元素的xor.然后xor这两件事你得到一个输出.

Answer 2

XOR语句具有'a'XOR'a'将始终为0的属性,即它们取消,因此,如果您知道您的列表只有一个副本,并且范围是x到y,601到607在你的情况下,将变量中x和y的所有元素的xor保持在一起是可行的,然后使用数组中的所有元素xor这个变量.由于只有一个元素会被复制,因此不会因为xor操作而被取消,这将是你的答案.

void main()
{
    int a[8]={601,602,603,604,605,605,606,607};
    int k,i,j=601;

    for(i=602;i<=607;i++)
    {
        j=j^i;
    }

    for(k=0;k<8;k++)
    {
        j=j^a[k];
    }

    printf("%d",j);
}

此代码将根据需要提供输出605!

Answer 3

记住XOR运算符的以下两个属性：

（1）如果对数字0（零）进行异或运算，它将再次返回相同的数字。

均值，n ^ 0 = n

（2）如果将数字与xor一起使用，它将返回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：在给定数组中找到“最小”和“最大”值。这将花费O（n）。

第2步：查找范围从“最小”到“最大”（包括）的所有整数的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 )