XOR 查找数组中的重复项

Question

我已经在这个线程中看到了这个问题的解决方案 -> 如何在打乱顺序的连续整数数组中找到重复元素？

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

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);

Answer 2

我猜这可能与 i 值与 arr[i] 相同这一事实有关，

就像这样做：

00000001 ^ 00000001

等于 00000000

我可能想错了，但这不会搞砸这个过程吗？

Answer 3

我想我明白发生了什么。您可能将循环更改为，

for(int i=0; i<11; i++)
  ...

因为您向循环添加了额外的元素。问题是它没有与 10 进行异或，而 10 不是数组中的数字。因此，该算法停止工作。

int arr[11] = {0,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;
}
a = a^arr[10];

cout<<a;

现在，它对 0 到 9 的数字进行 XOR 两次（等于 0），并再对 4 进行一次异或，因此结果应该是 4。