埃森哲面试问题 - 找到阵中唯一未配对的元素 [英] Accenture interview question - find the only unpaired element in the array
问题描述
您已经给定大小的数组 2N + 1
有 N
对整数(可 +已经
, -ve
或 0
)和一个未配对的元素
You have been given an array of size 2n+1
that have n
pair of integers (can be +ve
, -ve
or 0
) and one unpaired element.
你会如何找到配对的元素?
How would you find the unpaired element?
对用于复制。因此,(3,3)
是一对,(3,-3)
是不可以一对。
Pair means duplicate. So (3,3)
is a pair and (3,-3)
is not a pair.
推荐答案
取 XOR
所有元素。
在对将抵消为
a XOR a = 0
和的结果将是唯一的不成对元素作为
and the result will be the only unpaired element as
0 XOR a = a
如果它的好摧毁阵列可以 XOR
相邻的元素。一旦完成所述阵列的最后一个元件具有未配对元素:
If its okay to destroy the array you can XOR
adjacent elements. Once done the last element of the array has the unpaired element:
N = Num of elements in array.
for( i=1 to N )
arr[i] ^= arr[i-1];
print arr[N-1]
如果它不行摧毁阵列,你可以使用一个变量来保存结果:
If its not okay to destroy the array, you can make use of a variable to hold the result:
N = Num of elements in array.
Unpaired = arr[0];
for( i=1 to N )
Unpaired = Unpaired ^ arr[i];
print Unpaired
C函数做同样的:
C function to do the same:
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.
}
这篇关于埃森哲面试问题 - 找到阵中唯一未配对的元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!