Encontre uma duplicata na matriz de números inteiros

Esta foi uma pergunta da entrevista.

Foi-me dado um conjunto den+1 números inteiros do intervalo[1,n]. A propriedade da matriz é que ela possuik (k>=1) duplicados e cada duplicado pode aparecer mais de duas vezes. A tarefa era encontrar um elemento da matriz que ocorresse mais de uma vez na melhor complexidade possível de tempo e espaço.

Depois de uma luta significativa, eu orgulhosamenteO(nlogn) solução que levaO(1) espaço. Minha ideia era dividir o alcance[1,n-1] em duas metades e determine qual das duas metades contém mais elementos da matriz de entrada (eu estava usando o princípio Pigeonhole). O algoritmo continua recursivamente até atingir o intervalo[X,X] OndeX ocorre duas vezes e isso é uma duplicata.

O entrevistador ficou satisfeito, mas então ele me disse que existeO(n) solução com espaço constante. Ele generosamente ofereceu poucas dicas (algo relacionado a permutações?), Mas eu não tinha ideia de como chegar a essa solução. Supondo que ele não estivesse mentindo, alguém pode oferecer diretrizes? Eu procurei no SO e encontrei poucas variações (mais fáceis) desse problema, mas não essa específica. Obrigado.

EDIT: Para tornar as coisas ainda mais complicadas, o entrevistador mencionou que a matriz de entrada não deve ser modificada.