find数组中唯一未配对的元素
埃森哲面试问题：
你已经得到了一个大小2n+1的数组，它有n对整数（可以是+ve ， -ve或0 ）和一个不成对的元素。
你会如何find不成对的元素？
一对意味着重复 。 所以(3,3)是一对， (3,-3) 不是一对。
采取所有元素的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]
如果不能销毁数组，可以使用一个variables来保存结果：
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. }
具有XOR解决scheme的单行Linq示例：
在DotNetFiddle演示
public static void Main() { int[] tab = { 1, 2, 3, 2, 1 }; Console.WriteLine(GetSingle(tab)); } private static int GetSingle(IEnumerable<int> tab) { return tab.Aggregate(0, (current, i) => current ^ i); }
为了乐趣和利润
编辑：
这个片段的解释。
var a = 2; var b = 2; Console.WriteLine(a ^ b); // will print 0 // because x ^ x == 0 var c = 3; Console.WriteLine(a ^ b ^ c); // will print 3 // because 0 ^ x == x Console.WriteLine(0 ^ a); // guess the output // get it? :) // Now, lets aggregate this enumerable ;)
替代解决scheme，在O（n）和O（n）空间中查找所有唯一值：
初始化一个哈希表。
对于数组中的每个值，检查哈希表中是否存在该值，如果存在，则将其删除，如果不存在，则将其添加。
返回值是哈希表中的所有项目。
如果重复值可以重复多次，可以很容易地修改为使用字典。
这里有一个简单的LINQ解决scheme，可以很容易地扩展以提供每个独特元素的出现次数：
int[] numbers = { -1, 0, 1, 2, 3, 4, 5, 4, 3, 2, 1 }; var numberGroups = from n in numbers group n by n into g select new { Number = g.Key, IsPaired = g.Count() == 2 }; Console.WriteLine("Unpaired elements:"); foreach (var group in numberGroups) { if (!group.IsPaired) Console.WriteLine(group.Number); }
输出：
Unpaired elements: -1 0 5
最好的答案是XOR操作符。 另一种方式就是，如果允许对数组进行sorting，则对其进行sorting并比较相邻的整数。 这假设所有整数出现一次只有一个整数出现两次。
// Random array of integers int[] 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 // Cycle through array comparing adjacent values. for(int i = 0; i < arr.length; i++){ // This would mean the single number was the last element in the array. if(i == arr.length-1) singleNum = arr[i]; // If the adjacent elements are the same, skip foward. if(i < arr.length-1 && arr[i] == arr[i+1]) i ++; else // Otherwise, you found the single number. singleNum = arr[i]; }
在给定数组的所有元素中执行XOR
def unpaired(arr): result = 0 for i in arr: result = result^i return result
