Помогите решить задачу

Рейтинг: 0Ответов: 2Опубликовано: 19.12.2014

Дана последовательность чисел. Известно что все числа в ней встречаются четное количество раз, кроме одного, которое встречается нечетное количество раз. Напишите программу, которая находит это число. например: исходная последовательность:1,2,3,4,2,3,1,4,2,1,4,3,4,12,3,2,1,5,5,7,7,12,7,7,9,8,12,9,8 Искомое число :12

Ответы

▲ 3Принят

Это классическая задача которая решается с помощью xor (исключающего или). Все числа "ксорятся" последовательно. Благодаря свойствам xor, в конце будет нужно число. Это алгоритм имеет линейную сложность (в отличии от алгоритма @Sergiks , который имеет квадратичную сложность (или в лучшем случае n*ln(n))).

▲ 1

Можно идти по последовательности, и очередное число либо добавлять в массив, если его там ещё нет, либо стирать из массива, если такое там уже есть.

В конце в массиве останутся только те, которых нечётное число.

Пример на JS.