Найдите целое число, не происходящее дважды в массиве

Question

Найдите целое число, не происходящее дважды в массиве

Я пытаюсь решить эту проблему: В целочисленном массиве все числа происходят точно дважды, за исключением единственного числа, которое происходит точно однажды.

Простое решение состоит в том, чтобы отсортировать массив и затем протестировать на не повторение. Но я ищу лучшее решение, которое имеет временную сложность O (n).

6

c algorithm

задан Bill the Lizard 19 September 2012 в 22:24

1 ответ

Другие вопросы по тегам:

c algorithm

Похожие вопросы:

score 19 · Accepted Answer

Вы можете использовать операцию «XOR» на весь массив. Каждая пара номеров отменит друг друга, оставляя вас с искажем.

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;
}