Задача на поиск числа #751318

Есть огромный файл в несколько гигабайт, в котором записаны целые числа. Известно, что каждое число встречается два раза, но есть единственное число, которое встречается один раз. Предложите эффективный алгоритм для поиска этого числа. Как изменится алгоритм, если каждое число будет встречаться в файле чётное число раз, а единственное из них нечётное число раз?

отсортировать для начала.

Числа в ТЗ, добавить колонку с единичками, свернуть по первой колонке, отсортировать по второй колонке, выбрать первую строку, откусить булку, хлебнуть чаю...

Если нет ограничения на использование памяти, в лоб делается за один проход файла.

привести файл в вид, который способен проглотить булк инсерт, создать в скуле базу с единственной таблицей и единственной колонкой, скормить файл скулю, написать запрос...

если числа БЕЗ пропусков, то тупым вычислением можно узнать. Если с пропусками, то только перебором

+ в коллекцию добавляем при первом появлении и удаляем при втором, в конце в коллекции останется искомое

в худшем случае потребуется памяти в половину от файла

Берем очередное число из файла, пробегаем по файлу в поисках дубля. Удаляем из файла чтобы второй раз не проверять. И так со всеми числами. Для ускорения можно брать не одно, а блок чисел за один раз, смотря сколько памяти можно задействовать.

" а единственное из них нечётное число раз" - это как???

есть числа 1,2,3 которые повторяются 2 раза, 4 раза и т.д. а есть число 5 которое повторяется 3 раза, 5 или 7 и т.д. вот 5 ему нужно найти

ИМХО. Лучшее решение в . Хотя в не озвучены критерии определения эффективности.

применить, например, операцию XOR - на выходе будет искомое число