Алгоритм для поиска повторяющегося числа в списке, который может содержать любое количество повторов

Пожалуйста, внимательно прочитайте этот вопрос, прежде чем закрывать его как дубликат, хотя, если это честный дубликат, я буду рад узнать об этом. Это обобщение Найти любое из нескольких возможных повторяющихся целых чисел в списке.

Для любого набора S Nцелые числа и любой массив Aдлина N + 1, каждая запись которой взято из S, что лучше алгоритм для поиска некоторых (должно быть по крайней мере один) повторный ввод A?

ПРИМЕЧАНИЕ. В A может быть несколько повторяющихся записей, и любая запись может повторяться несколько раз.

Как указывает Немо, тривиальное решение занимает пространство O (1) и O (N ^ 2). Я ищу решение, которое улучшает время без ущерба для пространства. Если быть точным, то решение (ы), которое я ищу:

Возвращает значение a, которое появляется в A не менее двух раз,
Используется не более O (log N) без изменения A и
Принимает меньше O (N ^ 2) время

EDIT: набор S предназначен для обеспечения того, чтобы массив A имел хотя бы одну повторяющуюся запись. Для этой проблемы не предполагайте, что у вас есть S, предоставленный вам как упорядоченный набор. Вы можете запросить S (boolean для возврата true s в S и false в противном случае), и вы можете запросить A (вызов A [i]), но все. Любое решение, которое сортирует A или S, превышает пределы пробела.

Это обобщение делает недействительным решение указателя к исходному вопросу (у которого есть O (1) и O (N)), и ограничение пространства, которое я налагаю, делает недействительным решение fiver (которое имеет O (N) пространство и время),

Ответ 1

Этот алгоритм похож на Justin Simon's, но ключевым моментом является то, как вычислить медианный (или k-ый элемент) S, используя только O (1) пространство эффективно.

Вот этот ключевой алгоритм, который рандомизирован:

Установите меньшее значение, равное минимальному элементу S и верхнему, равному максимальному элементу S. Выберите случайный элемент x из S, который находится между нижним и верхним (это стоит не более O (n) ожидаемого времени). Вычислить ранг времени x (O (n)). Если x-ранг слишком низок, установите нижний предел на время x (O (n)), иначе установите верхний уровень, равный предшественнику времени x (O (n)). Повторяйте до тех пор, пока нижний не будет равен верхнему.

Обратите внимание, что каждая итерация стоит O (n) в ожидании и в ожидании есть итерации O (lg n), поэтому ожидаемая стоимость времени равна O (n lg n), а использование пространства - O (1), так как мы сохраняем только нижние и верхний.

Используя эту способность для выбора k-го элемента, мы можем затем использовать принцип pigeonhole, как предлагается в исходном вопросе, чтобы найти все более мелкие сегменты S, которые содержат слишком много элементы для всех различны, используя O (lg n) линейное сканирование пространств A и O (1) для хранения соответствующих сумм элементов в каждой области. Каждая такая итерация стоит O (n) в дополнение к стоимости O (n lg n) для нахождения k-го элемента и есть итерации O (lg n), поэтому общая стоимость равна O (n lg ^ 2 n).

Ответ 2

Найти среднюю точку множества S из N целых чисел (если они последовательны, это тривиально, иначе это можно сделать в O (logn)).

Пройдите через свой список A, подсчитайте количество записей, которые меньше этой средней точки. Таким образом, у вас есть либо больше записей в меньше, чем ваша средняя точка, чем есть отдельные числа в S, которые делают то же самое, или у вас меньше записей в меньше, чем ваша средняя точка и т.д. В первом случае записи будут меньше, чем средняя точка и повторите, в последнем возьмите те, которые больше или равны ему.

Это решение работает в n (log (n)) ^ 2 раза, я считаю.

Ответ 3

Автор Поиск повторяющихся элементов в массиве предполагает, что даже если бы было выделено множество бит для представления каждого возможного целого (a вполне управляемый 2 ^ 24 байтовый бит-массив дает один бит для каждого 32-битного целого) все равно будет определяться как использование O (1) пространства, и я склонен согласиться.

Следовательно, самый простой возможный алгоритм, который проверяет и устанавливает бит, представляющий каждое целое число, найденное в массиве, возвращая дублирующее целое число, если бит уже установлен, будет выполняться в O (n) времени и использовать O (1) пространство.

Ответ 4

Если мы сможем изменить массив, я думаю, что мы можем это сделать, используя сортировку buck в пространстве в O (n) и O (1) дополнительное пространство.

В частности, пройдите через каждый элемент в списке. Для каждого элемента проверьте, совпадает ли это число с индексом. Если нет, замените это число на элемент в индексе, пока индекс и номер не совпадут. Если вы видите одно и то же число в новом индексе, это дубликат.