c++ - 如何在数组中找到未耦合的整数？

Question

可能重复：
查找数组中未出现两次的整数
埃森哲面试问题 - 查找数组中唯一未配对的元素

给定一个奇数大小的整数数组。数组中的所有整数都出现两次，除了一个整数。如何以最有效（内存和复杂性）的方式找到这个解耦整数？

Answer 1

如果将它们全部异或，最终将得到唯一的（未耦合的）值。

这是因为xXOR对于所有值x都为零，而XOR是.x0xx

例如，以下程序输出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 建议的那样，将所有元素异或在一起将为您提供唯一的价值。

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等于零？深思熟虑:)