ыл вопрос для интервью.

Мне дали массивn+1 целые числа из диапазона[1,n], Свойство массива состоит в том, что он имеетk (k>=1) дубликаты, и каждый дубликат может появляться более двух раз. Задача состояла в том, чтобы найти элемент массива, встречающийся более одного раза, в наилучшей возможной временной и пространственной сложности.

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

Интервьюер был доволен, но потом он сказал мне, что существуетO(n) решение с постоянным пространством. Он щедро предложил несколько подсказок (что-то связанное с перестановками?), Но я понятия не имел, как придумать такое решение. Предполагая, что он не лгал, кто-нибудь может предложить руководство? Я искал SO и нашел несколько (более простых) вариантов этой проблемы, но не эту конкретную. Спасибо.

РЕДАКТИРОВАТЬ: Чтобы сделать вещи еще сложнее, интервьюер упомянул, что входной массив не должен быть изменен.