c - 查找数组中未出现两次的整数

Question

我正在尝试解决这个问题:在整数数组中，所有数字恰好出现两次，除了一个数字恰好出现一次。

一个简单的解决方案是对数组进行排序，然后测试是否不重复。但我正在寻找具有 O(n) 时间复杂度的更好解决方案。

Answer 1

您可以对整个数组使用“异或”运算。每对数字将相互抵消，为您留下所寻求的值(value)。

int get_orphan(int const * a, int len)
{
    int value = 0;
    for (int i = 0; i < len; ++i)
        value ^= a[i];

    // `value` now contains the number that occurred odd number of times.
    // Retrieve its index in the array.
    for (int i = 0; i < len; ++i)
    {
        if (a[i] == value)
            return i;
    }

    return -1;
}