Eliminación de duplicados de una matriz en C / C ++ en tiempo O (n)

Si la matriz está ordenada, entonces esta lógica podría aplicarse.

1. Tiene dos punteros (P1, P2) que apuntan al principio de la matriz.
2. Indicador de incremento P2. Compruebe si el valor apuntado por P2 y P1 son iguales.
3. En caso afirmativo, incremente más y llegue al punto donde los valores de P1 y P2 no sean iguales. Ahora ve al paso 5.
4. Si no, asigne P1 a P2 y repita desde el paso 2.
5. Ahora, quita los elementos entre P1 y P2. Asigna P2 a P1.

Repita el proceso hasta que llegue al punto final de la matriz.

Recorre la matriz y compara cada elemento con el elemento anterior. Si es lo mismo, sabes que es un duplicado. Mantenga otro puntero que copia cada elemento único dentro de la matriz. P.ej. 1,1,4,5,7,7,9,11

Mantenga dos punteros i y j al inicio de la matriz, es decir 1.
Utilice i para atravesar la matriz y j para realizar un seguimiento del elemento único. Inicialmente, 1 es único, así que copie una [i] a una [j] e incremente ambas.
El siguiente 1 es duplicado, por lo que solo se incrementa j.
Cuando se encuentran 4, es único, así que copie una [i] a una [j] (j apunta a la segunda, es decir, el duplicado 1) e incremente ambas.
Haz lo mismo hasta que cruce completamente la matriz.
a [0 … j] da todos los elementos únicos.

Complejidad: O (n)

Si conoce un valor máximo (MAX_INT_VALUE) para los ints y no le preocupan las limitaciones de memoria, esta es una solución un tanto creativa que me ayudó a superar una entrevista de trabajo:

 public int* removeDuplicates(int* array, int arraySize) { short indexMarkers [MAX_INT_VALUE]; int i = 0; for (i=0; i 0) { array[cursor] = i; cursor++; } } //resize array to be sizeof(int)*cursor return array; } 

La idea es que los valores de los elementos de la matriz sean los índices de la matriz indexMarkers. Entonces, simplemente está comprobando si el valor existía para generar la nueva matriz. Esto sería al menos O (2N) sin embargo.