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

我遇到了一篇文章如何在一个混洗的连续整数数组中找到一个重复的元素? 但后来意识到这很多输入失败了。

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

 #include  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; } 

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

来自原始问题:

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

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

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

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

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!

以下是原始问题中显示的代码,它与您的实现不同。 您已将其修改为使用局部变量而不是数组的最后一个成员,这会产生影响:

 for (int i = 1; i < 1001; i++) { array[i] = array[i] ^ array[i-1] ^ i; } printf("Answer : %d\n", array[1000]); 
 //There i have created the program to find out the duplicate element in array. Please edit if there are required some changes. int main() { int arr[] = {601,602,603,604,605,605,606,607}; //int arr[] = {601,601,604,602,605,606,607}; int n= sizeof(arr)/sizeof(arr[0]); for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { int res = arr[i] ^ arr[j]; if (res == 0) { std::cout<< "Repeated Element in array = "< 

// OR您输入HashTable和Hash函数时可以使用它
如果值大于,则可以计算哈希表中的值
在HashTable的特定索引处有一个值,那么你可以说数组中有重复的值。

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

(1)如果你取0(零)的数字的xor,它将再次返回相同的数字。

均值,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步:在给定数组中查找“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 )