C++ 在许多情况下，使用 XOR 运算符查找数组中的重复元素会失败
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10764286/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Using XOR operator for finding duplicate elements in a array fails in many cases
提问by Snehasish
I came across a post How to find a duplicate element in an array of shuffled consecutive integers?but later realized that this fails for many input.
我遇到了一篇文章如何在随机排列的连续整数数组中找到重复的元素？但后来意识到这对于许多输入都失败了。
For ex:arr[] = {601,602,603,604,605,605,606,607}
例如：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;
}
How can I modify this code so that the duplicate element can be found for all the cases ?
如何修改此代码以便在所有情况下都可以找到重复元素？
回答by usamec
From original question:
从原始问题：
Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice.
假设您有一个包含 1001 个整数的数组。整数按随机顺序排列，但您知道每个整数都在 1 到 1000（含）之间。此外，每个数字在数组中只出现一次，一个数字除外，它出现了两次。
It basically says, that algorithm only works when you have consecutive integers, starting with 1, ending with some N.
它基本上是说，该算法仅在您有连续整数时才有效，从 1 开始，以一些 N 结束。
If you want to modify it to more general case, you have to do following things:
如果要将其修改为更一般的情况，则必须执行以下操作：
Find minimum and maximum in array. Then calculate expected output (xor all integers between minimum and maximum). Then calculate xor of all elements in array. Then xor this two things and you get an output.
在数组中查找最小值和最大值。然后计算预期输出（xor 最小值和最大值之间的所有整数）。然后计算数组中所有元素的异或。然后对这两件事进行异或，你就会得到一个输出。
回答by Vishal Srivastav
Remember these two properties of XOR operator :
记住 XOR 运算符的这两个属性：
(1) If you take xor of a number with 0 ( zero ) , it would return the same number again.
(1) 如果你对一个带有 0 ( 零 ) 的数字进行异或，它会再次返回相同的数字。
Means , n ^ 0 = n
意思是，n ^ 0 = n
(2) If you take xor of a number with itself , it would return 0 ( zero ).
(2) 如果你对一个数进行异或运算，它会返回 0（零）。
Means , n ^ n = 0
均值，n ^ n = 0
Now , Coming to the problem :
现在，问题来了：
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 ).
Solution :
解决方案 ：
Step 1 : Find “min” and “max” value in the given array. It will take O(n).
步骤 1：在给定数组中找到“min”和“max”值。它将花费 O(n)。
Step 2 : Find XOR of all integers from range “min” to “max” ( inclusive ).
第 2 步：对从“min”到“max”（含）范围内的所有整数求异或。
Step 3 : Find XOR of all elements of the given array.
第 3 步：求给定数组的所有元素的异或。
Step 4 : XOR of Step 2 and Step 3 will give the required duplicate number.
第 4 步：第 2 步和第 3 步的 XOR 将给出所需的重复数。
Description :
描述 ：
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 )
回答by Ashwyn
A XOR statement has the property that 'a' XOR 'a' will always be 0, that is they cancel out, thus, if you know that your list has only one duplicate and that the range is say x to y, 601 to 607 in your case, it is feasible to keep the xor of all elements from x to y in a variable, and then xor this variable with all the elements you have in your array. Since there will be only one element which will be duplicated it will not be cancelled out due to xor operation and that will be your answer.
XOR 语句的属性是 'a' XOR 'a' 将始终为 0，即它们相互抵消，因此，如果您知道您的列表只有一个重复项并且范围是从 x 到 y，601 到 607在您的情况下，将 x 到 y 的所有元素的异或保留在变量中是可行的，然后将该变量与数组中的所有元素进行异或。由于只有一个元素将被复制，因此不会因异或运算而被取消，这将是您的答案。
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);
}
This code will give the output 605, as desired!
此代码将根据需要提供输出 605！
回答by Francis Upton IV
Here is the code shown in the original question, which is different than your implementation. You have modified it to use a local variable instead of the last member of the array, that makes a difference:
这是原始问题中显示的代码，它与您的实现不同。您已将其修改为使用局部变量而不是数组的最后一个成员，这会有所不同：
for (int i = 1; i < 1001; i++)
{
array[i] = array[i] ^ array[i-1] ^ i;
}
printf("Answer : %d\n", array[1000]);
回答by Yogendra Kumar
//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 = "<<arr[i]<<std::endl;
}
}
}
return 0;
}
//OR You can use HashTable and Hash Function when you enter the same
value into the hash table that time you can make count if its greater than
one value at particular index of HashTable then you can say that there are repeated value in the array.
//OR 您可以使用HashTable和Hash函数，当您将相同的
值输入到哈希表中时，如果
在HashTable的特定索引处大于一个值，则可以进行计数，那么您可以说数组中有重复的值。
回答by Palak Jain
Although the answers provided here are good, yet I'd like you to refer the answer by Mohit Jainif there is an ambiguity.
虽然这里提供的答案很好，但如果有歧义，我希望您参考Mohit Jain的答案。
The fact variable xor variable = zerocan be used to locate the duplicates present in the array precisely and easily. Hope that helps!
该事实variable xor variable = zero可用于精确且轻松地定位数组中存在的重复项。希望有帮助！
