配列内の結合されていない整数を見つける方法は？

Question

可能性の重複：奇数サイズの整数の配列を考えると
Find integer not occurring twice in an array
Accenture interview question - find the only unpaired element in the array

。配列内のすべての整数は、単一の整数を除いて2回表示されます。最も効率的な（メモリと複雑さの両方の）方法で、この結合されていない整数を見つける方法はありますか？

Answer 1

これらをすべてXORすると、孤立した（結合されていない）値になります。

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）の時間計算量、最小、平均および最悪のケースです。

Answer 2

paxが示唆しているように、すべての要素を一緒にXORすると、あなたの唯一の価値が得られます。

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もゼロに等しいか？思考のための食べ物：