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

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

Для любого набора 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 (логическое значение, чтобы вернуть true равно s в S и false в противном случае), и вы можете запросить A (позвоните по телефону A [i] ), но это все. Любое решение, которое сортирует A или S , превышает ограничение по пространству.

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