Edizione didattica italiana
Esercizi sugli array in C: elimina i duplicati
Elimina i duplicati da un array ordinato in C con due indici. Conserva i valori unici nello stesso array e stampa il loro numero e gli elementi risultanti.
Leggi N e un array di N interi ordinati in modo non decrescente. Elimina i valori ripetuti senza creare un secondo array. Conserva una sola occorrenza di ogni valore e stampa la nuova lunghezza e gli elementi unici.
Usa un indice di lettura e uno di scrittura. Se il valore letto è diverso dall’ultimo conservato, copialo in arr[write] e avanza la scrittura. Con N = 1 non cambia nulla; se tutti i valori sono uguali, ne resta uno.
Input
Prima riga: N. Seconda riga: N interi in ordine non decrescente.
Output
Prima riga: numero di valori unici. Seconda riga: questi valori separati da spazi.
Vincoli
- 1 <= N <= 1000
- -1000 <= arr[i] <= 1000
- L’input è ordinato in modo non decrescente.
- Usa O(1) di memoria ausiliaria.
Suggerimenti
- Conserva il primo elemento: N è almeno uno.
- Confronta ogni valore con l’ultimo conservato.
Codice sorgente
#include <stdio.h>
#define MAX_N 1000
int remove_duplicates(int arr[], int n) {
// TODO: Compact unique values into arr[0..write-1] and return write.
(void)arr;
return n;
}
int main(void) {
int n;
if (scanf("%d", &n) != 1 || n < 1 || n > MAX_N) return 1;
int arr[MAX_N];
for (int i = 0; i < n; ++i) {
if (scanf("%d", &arr[i]) != 1 || arr[i] < -1000 || arr[i] > 1000) return 1;
if (i > 0 && arr[i] < arr[i - 1]) return 1;
}
int length = remove_duplicates(arr, n);
printf("%d\n", length);
for (int i = 0; i < length; ++i) {
printf("%d%c", arr[i], i == length - 1 ? '\n' : ' ');
}
return 0;
}Spiegazione della soluzione
Inizia con write = 1. Leggi da read = 1; se arr[read] è diverso da arr[write - 1], copialo in arr[write] e incrementa write.
Stampa write e il prefisso di quella lunghezza. Il tempo è O(N) e la memoria ausiliaria O(1).
Codice della soluzione
#include <stdio.h>
#define MAX_N 1000
int remove_duplicates(int arr[], int n) {
int write = 1;
for (int read = 1; read < n; ++read) {
if (arr[read] != arr[write - 1]) {
arr[write] = arr[read];
++write;
}
}
return write;
}
int main(void) {
int n;
if (scanf("%d", &n) != 1 || n < 1 || n > MAX_N) return 1;
int arr[MAX_N];
for (int i = 0; i < n; ++i) {
if (scanf("%d", &arr[i]) != 1 || arr[i] < -1000 || arr[i] > 1000) return 1;
if (i > 0 && arr[i] < arr[i - 1]) return 1;
}
int length = remove_duplicates(arr, n);
printf("%d\n", length);
for (int i = 0; i < length; ++i) {
printf("%d%c", arr[i], i == length - 1 ? '\n' : ' ');
}
return 0;
}Domande frequenti
Perché il codice e alcuni risultati restano in inglese?
Parole chiave C, identificatori, commenti del programma e output attesi restano quelli originali per preservare codice eseguibile e test coerenti. Spiegazioni e istruzioni sono tradotte.