Eliminar duplicados de la matriz en tiempo lineal y sin matrices adicionales

Question

Tenemos una matriz y no está ordenada. Sabemos que el rango es [0, n].

Queremos eliminar duplicados pero no se puede utilizar matrices adicionales y debe ejecución en tiempo lineal.

¿Alguna idea? Solo para aclarar, ¡esto no es para la tarea!

Answer 1

Si los números enteros son 0 a n, puede moverse a través de la matriz, colocando números por sus índices. Cada vez que reemplazas un número, toma el valor que solía estar allí y muévelo a donde debería estar. Por ejemplo, supongamos que tenemos una matriz de tamaño 8:

----------------- 
|3|6|3|4|5|1|7|7| 
----------------- 
S 

Donde S es nuestro punto de partida, y vamos a utilizar C para realizar un seguimiento de nuestro índice "actual" a continuación. Comenzamos con el índice 0, y movemos 3 al punto del índice 3, donde 4 es. Ahorre 4 en una var. Temp.

----------------- 
|X|6|3|3|5|1|7|7| Saved 4 
----------------- 
S  C 

A continuación, poner 4 en el índice 4, el ahorro de lo que solía estar allí, 5.

----------------- 
|X|6|3|3|4|1|7|7| Saved 5 
----------------- 
S  C 

Sigue

----------------- 
|X|6|3|3|4|5|7|7| Saved 1 
----------------- 
S   C 

----------------- 
|X|1|3|3|4|5|7|7| Saved 6 
----------------- 
S C 

----------------- 
|X|1|3|3|4|5|6|7| Saved 7  
----------------- 
S   C 

Cuando tratamos de sustituir a 7, vemos un conflicto, entonces simplemente no lo colocamos. Continuamos a partir del índice de partida S, incrementarlo en 1:

----------------- 
|X|1|3|3|4|5|6|7| 
----------------- 
    S   

1 está muy bien aquí, 3 tiene que mover

----------------- 
|X|1|X|3|4|5|6|7| 
----------------- 
    S 

Pero 3 es un duplicado, por lo que tiramos a la basura y mantener iterando a través del resto de la matriz.

Básicamente, movemos cada entrada como máximo 1 vez e iteramos por toda la matriz. Eso es O (2n) = O (n)

Answer 2

¿Puedes ordenar? Ordene con Radix Sort - http://en.wikipedia.org/wiki/Radix_sort con complejidad O (arraySize) para el caso dado y luego elimine los duplicados de la matriz ordenada O (arraySize).

Answer 3

Supongamos que int a[n] es una matriz de enteros en el rango [0, n-1]. Tenga en cuenta que esto difiere ligeramente del problema establecido, pero hago esta suposición para dejar en claro cómo funciona el algoritmo. El algoritmo puede parchearse para trabajar en enteros en el rango [0, n].

for (int i=0; i<n; i++) 
{ 
    if (a[i] != i) 
    { 
     j = a[i]; 
     k = a[j]; 
     a[j] = j; // Swap a[j] and a[i] 
     a[i] = k; 
    } 
} 

for (int i=0; i<n; i++) 
{ 
    if (a[i] == i) 
    { 
     printf("%d\n", i); 
    } 
} 

Answer 4

void printRepeating(int arr[], int size) 
{ 
    int i; 
    printf("The repeating elements are: \n"); 
    for(i = 0; i < size; i++) 
    { 
    if(arr[abs(arr[i])] >= 0) 
     arr[abs(arr[i])] = -arr[abs(arr[i])]; 
    else 
     printf(" %d ", abs(arr[i])); 
    } 
} 

Answer 5

Walk través de la matriz asignar array [array [i]] = -array [array [i]]; si no negativo; si ya es negativo, entonces es duplicado, esto funcionará ya que todos los valores están dentro de 0 y n.

Answer 6

Extendiendo el código de @Joel Lee para que se complete.

#include <iostream> 
void remove_duplicates(int *a, int size) 
{ 
    int i, j, k; 
    bool swap = true; 

    while(swap){ 
    swap = false; 
    for (i=0; i<size; i++){ 
     if(a[i] != i && a[i] != a[a[i]]){ 
      j = a[i]; 
      k = a[j]; 
      a[i] = k; 
      a[j] = j; 
      swap = true;  
     } 

    } 
    } 
} 

int main() 
{ 
    int i; 
    //int array[8] = {3,6,3,4,5,1,7,7}; 
    int array[8] = {7,4,6,3,5,4,6,2}; 

    remove_duplicates(array, sizeof(array)/sizeof(int)); 

    for (int i=0; i<8; i++) 
     if(array[i] == i) 
      std::cout << array[i] << " "; 

    return 0; 
}