Задача: В очень большом целочисленном массиве (n > 10^9, |ai| <= 10^18) найти число, которое не повторяется (гарантируется, что оно есть и такое единственное).
Пример ввода:
7 11 26 7 11
вывод:
26
Если повторов каждого числа четное количество (кроме одного, которое нужно найти), то можно применить XOR последовательно ко всем элементам. А как можно быстро найти искомый элемент, если числа могут повторяться нечетное количество раз.
Пример ввода:
1 17 5 17 1 17
вывод:
5
UPD: Числа можно считывать повторно, они хранятся в файле, с которым можно делать все, что хочется. Ограничений на время и память нет.
Например, можно построить бор или применить цифровую (порязрядную) сортировку. Правда, тогда будет линейное количество памяти.
Вы правы. Но при n = 10^12 понадобится почти 8 Тб памяти. Я хотел бы узнать, возможно ли как-то сэкономить память?
Возможно, что есть решение, не использующее памяти как таковой (ну типа того, что с ксором), но если нет, то при N=10^12 ресурсов у вас не хватит (да и времени), а вообще же при N>10^9 вы в оперативную память этот массив не запихнете (ну при 10^9 еще сможете). Если же использовать внешнюю память, то нужно либо очень ветвистое B-дерево, либо же любой более-менее нормальный алгоритм внешней сортировки (многопутевое слияние например).
Примеры ввода-вывода не соответствуют условию.
Если надо найти число, которое повторяется один раз, то во втором примере это число 1, а в первом таких чисел 2: 7 и 11. Возможно, имелось в виду найти число, которое вообще не повторяется?
И вообще, обычно в таких случаях следует указывать источник задачи...
Да, я ошибся. Число, которое не повторяется.
UPD: Это измененная задача, которая мне встретилась в комментариях в ВК. В оригинале числа повторялись ровно 1 раз.
То есть, никто не гарантирует, что у неё вообще есть адекватное решение?
Верно. Выходит, что нужно жертвовать либо временем, либо памятью. Хотя, может быть, есть какое-то адекватное решение.
так как это не олимпиадная задача (хотя, подозреваю что задача с собеседования :), для пункта 2 можно воспользоваться утилитой
sortиз GNU Coreutils. Там куча опций, например можно сжимать временные файлыЗадачу точно можно решить за O(n) времени и памяти :) Судя по ограничениям, задача вряд ли олимпиадная, а потому хотелось бы подробнее про ограничения. Например, разрешается ли использовать внешнюю память. Программа каким-то образом получает этот массив, считывая или генерируя. Можно ли, например, тогда его повторно считывать?
Ограничений никаких нет. Хочется узнать оптимальное решение.
Если числа хранятся в файле, который можно считывать повторно, можно решить за О(1) памяти и О(n^2) времени.
Заводим переменные х, c и t. Изначально х=0. На каждой итерации мы увеличиваем х на 1, пока оно не достигнет n.
В t считываем a[i]. Если i<x, идём дальше. Если i==x, запоминаем a[i] в с. Если i>x, проверяем, равны ли a[i] и с. Если да, обрываем цикл считывания, увеличиваем х на 1 и считываем значение заново. Если мы дошли до конца файла, то c — наш искомый элемент.
Солнце раньше Землю поглотит, чем эта программа закончит работать.
Зато не нужно 8 Тб памяти...
Ну как выше упомянули, используя файловую сортировку эту задачу можно за O(n*log(n)). И в смысле оперативной памяти можно обойтись O(1)
А откуда 8 тб?
Если нигде не ошибся, то и оперативки на хорошем компе хватит, чтобы все скидывать в in memory хеш таблицу)
n может быть больше 10^9. При n = 10^12 будет почти 8Тб.
Не, это бред.
Ещё есть вариант. Сортировать черпаком. Заводим массив
long long count[2000000000000000000]проходим по массиву *aи всё. На мой взгляд оптимизации расположены по важности именно так: 1) по времени работы программы 2) по кол-ву используемой памяти 3) по кол-ву кода. Позтому я считаю, что главное время работы проги, а не память. Тем более, что Вы сказали, что память и время не ограничены.
Массив маленький.
А по-моему std::sort(a, a + n) куда быстрее и по времени, и по памяти, и по кол-ву кода.
O(n) этого метода против O(nlogn) стандартной сортировки.
O(1e18) этого метода против O(nlogn) стандартной сортировки.
Упс ^.^
Ну... Формально, 1е18 это константа. О(n+C)=O(n)
Если вообще память не ограничивать, то можно завести массив 2^64 элементов по 2 бита (0 — число не попадалось, 1 — 1 раз, 2 — 2 и более раз). Но понадобится памяти 2^22 ТБ (=2 ЭБ), так что давайте не будем отходить от реальности =)
Если бы все числа повторялись ровно 2 раза, или хотя бы четное число раз, то решение — это побитовый xor всех чисел. Указанный метод можно обобщить до "каждое число встречается k раз, а одно — строго меньше k". Но как решать в такой фоомулировке — хз.
Теперь понял. Спасибо =)
Обобщить не значит применить точно так же. Если каждое число, кроме одного, встречается k раз необходимо каждое число предстааить в двоичной системе счисления и сложить каждый разряд пл модулю k
Fefer_Ivan имел, наверное, ввиду, что нам нужно не обычный XOR, а суму каждого бита по модулю К в К-ичной системе. А также одно число не меньше К раз, а ровно один раз.
посчитать двоичную сумму (xor pascal) всех элементов, результат и будет искомым числом. был не внимателен, не прокатит.
Если задача стоит исключительно практическая то можно воспользоваться map-reduce. Сделав стандартный подсчет частот. А так как нам надо хранить этот массив хоть так хоть так то в DFS будет разумнее его хранить.
Можно сделать некую аналогию ручным способом. Будем проходить по файлу много раз Т (надо подбирать сколько) и каждый раз обрабатывать только числа которые дают определенный остаток при делении на Т, тогда можно заводить bitset и делать в тупую. Тогда по памяти будет N / (8 * T) байт. По времени будет Т * N.
Можно считывать по 10^7 (чем больше, тем лучше) элементов, сортировать их (стандартной сортировкой) записывать в новый файл, потом считывать с этого файла и досортировать слиянием с использованием еще 1 файла, а там уже ясно. выходит О(n) памяти и O(n*logn) времени.
Пока вроде бы два варианта предложили.
1. сортировка
2. хеш-таблица
Есть еще пограничный вариант: Сначала слегка посортировать т.е. разбить массив на K подмассивов так, что сортировка не требует перестановки чисел между различными подмассивами. Это можно сделать за N log K quicksort'ом который выходит когда массив становится меньше N / K. Потом строить хеш-таблицы для несортированных кусков. Ну еще не забыть про числа на границах кусков.
ещё есть недерминированный вариант с выбором случайной хеш функции.
H достаточно взять порядка N / 2 (делить на два ибо почти все числа повторяются) чтобы вероятность найти ответ за одну итерацию была порядка 1 / e ( e — число эйлера 2.71828...)
UPD: Это O(N) в среднем.
Еще можно юзать Perfect Hashing, тогда гарантированно хватит 2 проходов.
Думаю, это самый удачный вариант. Спасибо за ответ!
Меня давно интересует вопрос, каким образом лучше всего подбирать случайную хэш-функцию. Думаю, об этом где-то написано, но я не знаю где. Ибо лучше способа, чем "прибавить a, умножить на b, сдвинуть на c бит влево, где a, b и c — случайные числа" я не знаю. Не подскажете, как будет правильнее?
http://en.wikipedia.org/wiki/Zobrist_hashing Для примера заводим массив случайных 64-битных чисел zorb[n,b] Рассматриваем число как последовательность цифр. n-количество десятичных разрядов в числе, b=10 — [0..9] Первое измерение в массиве — позиция, второе — сама цифра. Само значение хеш-функции XOR по всем цифрам в числе.
Ну я не то чтобы экперт в этом, но думаю тут от задачи зависит. Условимся для начала, что нам нужна хеш-функция общего назнечения, не криптографическая. Можно использовать многочлены по модулю 2, как в crc32. Если построить таблицы и добавлять сразу по 8-16 байт, то выходит довольно быстрая функция (см. crc32) Многочлен можно выбирать случайно из множества неразложимых, они ищутся примерно также как простые числа. Можно использовать какой-нибудь блочный шифр например ГОСТ 28147-89, и ключ выбирать случайным образом. Но такая функция будет медленная. Можно использовать некоторое подобие блочного шифра, где количество раундов уменьшено, ибо нам нужна скорость, а криптографические свойства нет. Здесь очень много вариантов.