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

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 )

   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.

}

Answer 2

具有XOR解决方案的单行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 ;)

Answer 3

最好的答案是XOR运算符。只是为了好玩，如果允许对数组进行排序，可以对它进行排序并比较相邻的整数。假定所有整数恰好出现两次，一个整数出现一次。

// 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];

}