埃森哲面试问题:
你得到了一个大小为 2n+1
的数组,其中有 n
对整数(可以是 +ve
, -ve
或 0
) 和一个不成对的元素。
如何找到不成对的元素?
对表示重复。所以 (3,3)
是一对而 (3,-3)
不是一对。
最佳答案
对所有元素进行异或
。
这些对将抵消
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.
}
关于algorithm - 找到数组中唯一不成对的元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2644179/