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.