вторник, 14 сентября 2010 г.

Решение задачи о поиске двух недублирующихся элементов в потоке

Всем привет. Нашел, наконец-то, красивое решение задачи о поиске 2-ух недублирующихся элементов в большом входном потоке целых чисел (см. концовку моего предыдущего поста). Своим умом, к сожалению, до этого решения не дошел, но так как решение очень красивое, и мне оно понравилось, привожу его ниже (кстати, еще раз убедился во вменяемости практически абсолютного большинства участников форума rsdn.ru :).

Итак, напомню условие задачи. Есть большой входной поток целых чисел, про который известно, что в нем все числа дублируются кроме двух. Найти эти 2 числа за константное количество проходов с использованием константного количества памяти.