找到数组中唯一的未配对元素

Question

埃森哲面试问题:

您已经获得了一个大小数组,2n+1其中包含n一对整数(可以是+ve,-ve或0)和一个不成对的元素.

你怎么会找到不成对的元素？

对意味着重复.所以(3,3)是一对和(3,-3)是不是一对.

Answer 1

采取XOR的所有元素.

这对将取消为

a XOR a = 0

结果将是唯一不成对的元素

0 XOR a = a

如果它可以摧毁阵列你可以XOR相邻的元素.完成后,数组的最后一个元素具有未配对的元素:

N = Num of elements in array.
for( i=1 to N )
   arr[i] ^= arr[i-1];    
print arr[N-1]

如果不能销毁数组,可以使用变量来保存结果:

N = Num of elements in array.
Unpaired = arr[0];
for( i=1 to N )
   Unpaired = Unpaired ^ arr[i];    
print Unpaired

C函数做同样的事情:

int findUnpaired(int *arr,int len) {
 int i;                  // loop counter.
 int unpaired;           // to hold the unpaired element.

 unpaired = arr[0];      // initialize it with the 1st array ele.

 for(i=1;i<len;i++) {    // loop for all remaining elements.
    unpaired ^= arr[i];  // XOR each element with the running XOR.
 }
 return unpaired;        // return result.
}