问题描述
重点访谈问题：
您得到的数组大小为 2n + 1 c $ c> n 对整数（可以是 + ve ， -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.
}
这篇关于查找数组中唯一未配对的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！