c++ - 异或查找数组中的重复项

Question

我已经在这个线程中看到了这个问题的解决方案 -> How to find a duplicate element in an array of shuffled consecutive integers?

但我现在遇到的问题与它几乎没有什么不同。

int arr[10] = {1,2,3,4,5,6,7,8,4,9};
    int a= 0;
    for(int i=0;i<10;i++) {
     a= a^ arr[i] ^i;
    }
    cout<<a;

考虑上面提到的代码片段。一切正常。但是当我向上面提到的数组添加 0 时，int arr[11] = {0,1,2,3,4,5,6,7,8,4,9};我没有得到正确的重复元素。有人可以纠正我在这里犯的错误吗？

Answer 1

这个技巧依赖于介于 1 和 n 之间的值。如果数字在其他范围内，您将不得不抵消它们。

static const int n = 11;
int arr[n] = {0,1,2,3,4,5,6,7,8,4,9};
int offset = 1;
int a= 0;
for(int i=0;i<n;i++) {
 a= a^ (arr[i]+offset) ^i;
}
cout<< (a-offset);