Rimuovere duplicati da un array in C

Rimuovere duplicati da un array è una delle operazioni di manipolazione dei dati fondamentali in informatica. Questa operazione è essenziale in molti contesti applicativi, come la pulizia dei dati, l'ottimizzazione delle query sui database, e la gestione efficiente delle strutture dati.

In questa pagina, esploreremo diverse tecniche per rimuovere duplicati da un array in C, esaminando sia soluzioni semplici che più complesse.

Dato un array di numeri interi, il nostro obiettivo è rimuovere tutti gli elementi duplicati in modo che ogni numero appaia una sola volta. Ad esempio, dato l'array {1, 2, 2, 3, 4, 4, 5}, l'output desiderato è {1, 2, 3, 4, 5}.

Soluzione di base: Utilizzo di un secondo array

Un approccio semplice per risolvere questo problema è utilizzare un secondo array per memorizzare gli elementi unici. Questo metodo ha una complessità temporale di O(n²) a causa della necessità di confrontare ogni elemento con tutti gli altri elementi già presenti nel secondo array.

Ecco una semplice implementazione che utilizza un secondo array:

#include <stdio.h>

void removeDuplicates(int arr[], int n) {
    int temp[n];
    int j = 0;

    // Itera attraverso l'array originale
    for (int i = 0; i < n; i++) {
        int k;
        // Verifica se arr[i] è già presente in temp
        for (k = 0; k < j; k++) {
            if (arr[i] == temp[k]) {
                break;
            }
        }
        // Se non è presente, aggiungilo a temp
        if (k == j) {
            temp[j] = arr[i];
            j++;
        }
    }

    // Copia gli elementi unici nell'array originale
    for (int i = 0; i < j; i++) {
        arr[i] = temp[i];
    }

    // Stampa l'array risultante
    for (int i = 0; i < j; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    removeDuplicates(arr, n);

    return 0;
}

Analisi del codice

int temp[n];

temp è un array temporaneo utilizzato per memorizzare gli elementi unici.

for (int i = 0; i < n; i++) {
    int k;
    for (k = 0; k < j; k++) {
        if (arr[i] == temp[k]) {
            break;
        }
    }
    if (k == j) {
        temp[j] = arr[i];
        j++;
    }
}

Per ogni elemento in arr, controlliamo se è già presente in temp. Se non è presente, lo aggiungiamo a temp.

for (int i = 0; i < j; i++) {
    arr[i] = temp[i];
}

Copiamo gli elementi da temp a arr fino a j, che rappresenta il numero di elementi unici.