Effizient die Reihenfolge der Wörter in einem Zeichenarray umkehren

Die Umkehrung der Reihenfolge der Wörter in einem Zeichenarray ist ein klassisches Problem, das Ihr Verständnis von Algorithmen und String-Manipulation testet. Ob Sie sich auf ein Vorstellungsgespräch vorbereiten oder einfach nur Ihre Programmierskills verfeinern möchten, die Beherrschung dieser Herausforderung ist äußerst lohnend. In diesem Beitrag werden wir das Problem detailliert untersuchen und eine effiziente Lösung in C/C++ aufschlüsseln.

Das Problem

Gegeben ist ein Array von Zeichen, das einen Satz bildet, und wir wollen die Reihenfolge der Wörter umkehren, ohne die einzelnen Buchstaben in den Wörtern zu verändern. Zum Beispiel, wenn Sie eingeben:

"dies ist ein String"

Sollte die Ausgabe sein:

'String ein ist dies'

Die Herausforderung gibt vor, dass diese Operation in O(N) Zeit und O(1) Speicher erreicht werden soll, was bedeutet, dass Funktionen wie split() oder Datenstrukturen wie Stapel, die zusätzlichen Speicher manipulieren, nicht verwendet werden dürfen.

Analyse des Problems

Zeitkomplexität

Die Anforderung einer O(N) Zeitkomplexität bedeutet, dass der Algorithmus einen linearen Durchgang durch die Daten machen muss. Daher sollten wir verschachtelte Schleifen vermeiden, die die Zeitkomplexität erhöhen.

Raumkomplexität

Für eine O(1) Raumkomplexität dürfen wir keine zusätzlichen Datenstrukturen für die Speicherung verwenden. Das bedeutet, dass die Operationen direkt im Eingabearray stattfinden müssen.

Die Lösung

Lassen Sie uns die Lösung Schritt für Schritt aufschlüsseln. Wir werden einen Ansatz mit zwei Durchgängen nutzen, um dieses Problem effizient zu lösen.

Schritt 1: Das gesamte Zeichenarray umkehren

Der erste Schritt besteht darin, das gesamte Array umzukehren. Dadurch wird der ursprüngliche String in einen String umgewandelt, in dem alle Zeichen umgekehrt sind. Für unser Beispiel "dies ist ein String" nach der Umkehrung:

"gnirtS ni e ni sti e id"

Schritt 2: Jedes Wort umkehren

Nachdem wir den gesamten String umgekehrt haben, müssen wir jedes einzelne Wort umkehren, um sie wieder in die richtige Reihenfolge zu bringen. So können wir diese Schritte in C/C++ implementieren:

void swap(char* str, int i, int j) {
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length) {
    for(int i = 0; i < length / 2; i++) {
        swap(str, i, length - i - 1);
    }
}

void reverse_words(char* str) {
    int l = strlen(str);
    // Umkehren des gesamten Strings
    reverse_string(str, strlen(str));
    int p = 0;
 
    // Wortgrenzen finden und wortweise umkehren
    for(int i = 0; i < l; i++) {
        if(str[i] == ' ') {
            reverse_string(&str[p], i - p);  // Umkehren des identifizierten Wortes
            p = i + 1;
        }
    }
    // Schließlich das letzte Wort umkehren.
    reverse_string(&str[p], l - p);
}

Erklärung des Codes

1. Swap-Funktion: Wir verwenden eine Hilfsfunktion swap, um Zeichen im Array zu vertauschen.
2. Reverse String-Funktion: Diese Funktion kehrt die Zeichen des Strings mithilfe der Swap-Funktion um.
3. Reverse Words-Funktion: Die Hauptfunktion kehrt zunächst das gesamte Zeichenarray um und iteriert dann durch es, um einzelne Wörter zu umkehren, die durch Leerzeichen identifiziert werden. Das letzte Wort wird nach dem Ende der Schleife behandelt.

Komplexitätsanalyse

Die Umkehrung des Arrays in zwei Durchgängen ergibt eine Zeitkomplexität von O(N):

• Erster Durchgang: O(N) für die Umkehrung des gesamten Strings.
• Zweiter Durchgang: O(N) für die Umkehrung jedes Wortes.

Somit bleibt die endgültige Zeitkomplexität O(N). Die Raumkomplexität beträgt O(1), da kein zusätzlicher Platz genutzt wird, außer für Iterationsvariablen.

Fazit

Die effiziente Umkehrung der Reihenfolge von Wörtern in einem Zeichenarray erfordert eine Kombination aus String-Manipulationen und einem Verständnis des indizierten Zugriffs. Der hier vorgestellte Algorithmus zeigt einen klaren Ansatz, der die Anforderungen an Zeit O(N) und Raum O(1) erfüllt, während er in C/C++ implementiert ist. Üben Sie diese Lösung, und Sie werden feststellen, dass sie eine hervorragende Ergänzung zu Ihrem Programmierwerkzeugkasten ist!