174
правки
Изменения
→Решение за O(N)
== Решение за O(N) ==
Алгоритм можно представить следующим образом: пусть на вечеринке собрались <tex>N</tex> людей, и каждому из них соответствует один элемент из массива. Когда встречаются двое с разными элементами, то они образуют пару и садятся. В конце концов останутся стоять только гости люди с одинаковыми элементами. Это и есть искомый элемент.
Будем идти по массиву и запоминать элемент, для которого еще не нашлось пары. При встрече такого же элемента увеличиваем счетчик "без пары", иначе - уменьшаем. Если все элементы уже имеют пару, то говорим, что у текущего элемента пары нет.
