Deutsche Lernausgabe
C-Array-Übungen: Duplikate entfernen
Entferne Duplikate aus einem sortierten C-Array mit zwei Indizes. Speichere eindeutige Werte im selben Array und gib ihre Anzahl und die Werte aus.
Lies N und ein Array mit N aufsteigend sortierten ganzen Zahlen ein; gleiche Werte sind erlaubt. Entferne Wiederholungen ohne ein zweites Array. Behalte jeden Wert einmal und gib die neue Länge und die eindeutigen Elemente aus.
Verwende einen Lese- und einen Schreibindex. Unterscheidet sich der gelesene Wert vom zuletzt behaltenen Wert, kopiere ihn nach arr[write] und erhöhe den Schreibindex. Bei N = 1 bleibt alles gleich; bei gleichen Werten bleibt ein Element.
Eingabe
Erste Zeile: N. Zweite Zeile: N aufsteigend sortierte ganze Zahlen; gleiche Werte sind erlaubt.
Ausgabe
Erste Zeile: Anzahl eindeutiger Werte. Zweite Zeile: diese Werte, durch Leerzeichen getrennt.
Vorgaben
- 1 <= N <= 1000
- -1000 <= arr[i] <= 1000
- Die Eingabe ist aufsteigend sortiert; gleiche Werte sind erlaubt.
- Verwende O(1) zusätzlichen Speicher.
Hinweise
- Behalte das erste Element: N ist mindestens eins.
- Vergleiche mit dem zuletzt behaltenen Wert.
Quellcode
#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;
}Erklärung der Lösung
Starte mit write = 1. Lies ab read = 1; falls arr[read] von arr[write - 1] abweicht, kopiere es nach arr[write] und erhöhe write.
Gib write und das Präfix dieser Länge aus. Laufzeit O(N), zusätzlicher Speicher O(1).
Lösungscode
#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;
}Häufige Fragen
Warum bleiben Code und manche Ausgaben englisch?
C-Schlüsselwörter, Bezeichner, Programmkommentare und erwartete Ausgaben bleiben wie im Original, damit der Code ausführbar und die Tests konsistent bleiben. Erklärungen und Aufgabenstellungen sind übersetzt.