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

Question

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

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

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

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

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

РЕДАКТИРОВАТЬ: Набор S предназначен для того, чтобы массив A имелхотя бы одна повторная запись.Для этой проблемы не думайте, что у вас есть S , предоставленный вам в качестве упорядоченного набора.Вы можете запросить S (логическое значение для возврата true равно s в S и false в противном случае), и вы можете запросить A (вызов A [i] ), но это все.Любое решение, которое сортирует A или S , превышает ограничение по пространству.

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

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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