А вот задачка на выходные! Она плохо подходит, чтобы спрашивать на собеседовании, потому что слишком уж на инсайт (пожалуйста, никогда не задавайте такие задачки на собеседованиях), и слишком простая для соревнований. Как раз чтобы доставить тот самый satisfying click в мозгу, за который мы любим программирование. Итак:
Есть большой массив из N 32-битных чисел. Каждое число встречается два раза, а два числа -- по одному. Найти эти два числа за один проход по массиву с константными затратами памяти (то есть не зависящими от размера массива).
Не забывайте использовать тег <spoiler> для решений в комментариях!
тривиальное решение: заводим нулевой битовый массив на 4Г битов (константная память!). если мы видим какое-то число то делаем на его позиции исключающее или с единицей. в конце только два бита будут равны одному — это и есть те числа что мы искали. в один проход по дополнительному массиву можно их найти.
Не троллить 🙂 Давайте, чтобы не было разночтений — памяти у вас четыре килобайта.
Disclaimer: пост написан на основе изрядно отредактированных логов чата closedcircles.com, отсюда и стиль изложения, и наличие уточняющих вопросов.
ссылка на оригинал статьи https://habrahabr.ru/post/280192/
Добавить комментарий