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

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 )&nbsp; &nbsp;arr[i] ^= arr[i-1];&nbsp; &nbsp;&nbsp;print arr[N-1]如果无法销毁该数组，则可以使用变量保存结果：N = Num of elements in array.Unpaired = arr[0];for( i=1 to N )&nbsp; &nbsp;Unpaired = Unpaired ^ arr[i];&nbsp; &nbsp;&nbsp;print UnpairedC函数做同样的事情：int findUnpaired(int *arr,int len) {&nbsp;int i;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // loop counter.&nbsp;int unpaired;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// to hold the unpaired element.&nbsp;unpaired = arr[0];&nbsp; &nbsp; &nbsp; // initialize it with the 1st array ele.&nbsp;for(i=1;i<len;i++) {&nbsp; &nbsp; // loop for all remaining elements.&nbsp; &nbsp; unpaired ^= arr[i];&nbsp; // XOR each element with the running XOR.&nbsp;}&nbsp;return unpaired;&nbsp; &nbsp; &nbsp; &nbsp; // return result.}

Answer 2

具有XOR解决方案的单行Linq示例：DotNetFiddle上的演示public static void Main(){&nbsp; &nbsp; int[] tab = { 1, 2, 3, 2, 1 };&nbsp; &nbsp; Console.WriteLine(GetSingle(tab));}private static int GetSingle(IEnumerable<int> tab){&nbsp; &nbsp; return tab.Aggregate(0, (current, i) => current ^ i);}为了乐趣和利润编辑：此代码段的说明。var a = 2;var b = 2;Console.WriteLine(a ^ b); // will print 0// because x ^ x == 0var c = 3;Console.WriteLine(a ^ b ^ c); // will print 3// because 0 ^ x == xConsole.WriteLine(0 ^ a); // guess the output// get it? :)// Now, lets aggregate this enumerable ;)

Answer 3

最好的答案是XOR运算符。只是为了好玩，如果允许对数组进行排序，可以对它进行排序并比较相邻的整数。假定所有整数恰好出现两次，一个整数出现一次。// Random array of integersint[] arr = {1, 2, 3, 4, 5, 6, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9};// Sort the array.Arrays.sort(arr);// Array now looks like: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 9&nbsp;// Cycle through array comparing adjacent values.for(int i = 0; i < arr.length; i++){&nbsp; &nbsp; // This would mean the single number was the last element in the array.&nbsp; &nbsp; if(i == arr.length-1)&nbsp; &nbsp; &nbsp; &nbsp; singleNum = arr[i];&nbsp; &nbsp; // If the adjacent elements are the same, skip foward.&nbsp;&nbsp; &nbsp; if(i < arr.length-1 && arr[i] == arr[i+1])&nbsp; &nbsp; &nbsp; &nbsp; i ++;&nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; // Otherwise, you found the single number.&nbsp; &nbsp; &nbsp; &nbsp; singleNum = arr[i];}