如何在數組中找到未耦合的整數？

可能重複：
Find integer not occurring twice in an array
Accenture interview question - find the only unpaired element in the array 如何在數組中找到未耦合的整數？

鑑於奇數大小的整數數組。除了一個整數外，數組中的所有整數都會出現兩次。如何以最有效的方式（內存和複雜性）找到這個未耦合的整數？

來源

2012-04-12 aviad

如果您將所有這些元素異或，最終會得到唯一（uncoupled）值。

這是因爲x XOR x是所有x值爲零，0 XOR x是x。

通過舉例的方式，下面的程序輸出99：

#include <stdio.h> 
int main (void) { 
    int num[] = { 1, 2, 3, 4, 5, 99, 1, 2, 3, 4, 5}; 
    unsigned int i; 
    int accum; 

    for (accum = 0, i = 0; i < sizeof(num)/sizeof(*num); i++) 
     accum ^= num[i]; 

    printf ("%d\n", accum); 

    return 0; 
}

在效率方面，它基本上是O（1）的空間和O（n）的時間複雜度，最小，平均和最壞的情況。

來源

2012-04-12 05:55:35 paxdiablo

如果數字是零怎麼辦？ – 2012-04-12 06:22:11

@Guarav，那麼你會得到零，如預期。嘗試一下。在上面的代碼中更改99並讓呃rip :-) – paxdiablo 2012-04-12 06:22:59

是的，沒錯，就是運行它。謝謝:) ... +1 – 2012-04-12 06:36:15

正如大家所建議的，將所有元素異或會使您獲得唯一的價值。

int getUncoupled(int *values, int len) 
{ 
    int uncoupled = 0; 
    for(int i = 0; i < len; i++) 
     uncoupled ^= values[i]; 
    return uncoupled; 
}

然而，這裏有一個小小的警告：沒有非耦合值和一個非耦合值爲零的集合有什麼區別？ x^x^y^y = 0但不x^x^0^y^y也等於零？食物的思想:)

來源

2012-04-12 06:04:22

輸出沒有任何區別，但是，鑑於規格「奇數大小」和「數組中的所有整數都出現兩次，除了一個整數」，「x^x^y^y '是不可能的。 – paxdiablo 2012-04-12 06:06:24

我的錯誤，我更多意味着如果陣列不是奇怪的大小。鑑於這是一個問題約束，我想我指出這是無關緊要的。 – 2012-04-12 06:13:59

如何在數組中找到未耦合的整數？

回答

相關問題