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.

Descrizione del problema

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^2) a causa della necessità di confrontare ogni elemento con tutti gli altri elementi già presenti nel secondo array.

Implementazione in C

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

Dichiarazione del secondo array:

int temp[n];

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

Verifica dei duplicati:

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.

Copia degli elementi unici:

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.

Indice pagine linguaggio C: