Seamos honestos, esta es una pregunta hw.

La pregunta en su totalidad:

Implemente un algoritmo de eliminación duplicado en una matriz unidimensional utilizando C ++ / Java en O (n) complejidad de tiempo sin espacio adicional. Por ejemplo, si la matriz de entrada es {3,5,5,3,7,8,5,8,9,9}, la salida debería ser {3,5,7,8,9}.

Lo he pensado durante bastante tiempo y aún no he podido resolverlo.

Mis pensamientos:

Podría eliminar duplicados en O (n) si se ordenara la matriz. Pero el algoritmo de clasificación más rápido que conozco tiene una complejidad O (n * log (n)).

Un algoritmo que se clasifica en O (n) es la clasificación bin o bucket. El problema aquí es que no se puede implementar sin usar espacio adicional.

Me pregunto si es posible en absoluto.

He investigado un poco y no he encontrado nada nuevo.

Gracias por cualquier ayuda.

PD: Le hubiera dado más tiempo si no fuera por el examen de mañana.