埃森哲面試題：您已被給定尺寸的陣列2n+1具有n對整數（可以是+ve，-ve或0）和一個未配對的元件。您將如何找到未配對的元素？對表示重復。所以(3,3)是一對，(3,-3)而不是一對。
3 回答
ITMISS
TA貢獻1871條經驗 獲得超8個贊
采取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.
}
波斯汪
TA貢獻1811條經驗 獲得超4個贊
具有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 ;)
天涯盡頭無女友
TA貢獻1831條經驗 獲得超9個贊
最好的答案是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];
}
添加回答
舉報
0/150
提交
取消